How to generate all combinations given an array of elements using backtracking?

Question

Given an array, generate all combinations

For example:

Input: {1,2,3}

Output: {1}, {2}, {3}, {1,2}, {2,1}, {1,3}, {3,1}, {2,3}, {3,2}, {1,2,3}, {1,3,2}, {2,1,3}, {2,3,1}, {3,1,2}, {3,2,1}

I am practicing Backtracking algorithms and I think I understand the general idea of backtracking. You are essentially running a DFS to find the path that satisfies a condition. If you hit a node that fails the condition, exit the current node and start at the previous node.

However, I am having trouble understanding how to implement the traverse part of the implicit tree.

My initial idea is to traverse down the left most path which will give me {1}, {1,2}, {1,2,3}. However, once I backtrack to 1, how do I continue adding the 3 to get {1,3} and {1,3,2} afterwards? Even if I have 2 pointers, I would need it to point to the 2 to eventually get {1,3,2}.

What steps should I take to solve backtracking questions such as this one?

Thanks for all the response. Here the algorithm that I came up with.

    public static void main(String[] args){
    char[] arr = {'1', '2', '3'};

    List<List<Character>> ans = new ArrayList<>();

    List<Character> combination = new ArrayList<>(3);

    Queue<Character> queue = new LinkedList<>();

    for(Character ch : arr){
        queue.add(ch);
    }

    Combination comb = new Combination();

    comb.solve(0, arr, queue, combination, ans);

    print(ans);
}


    public void solve(int index, char[] arr, Queue<Character> queue,  List<Character> combination, List<List<Character>> ans){
    if(index == arr.length){
        return;
    }else{
        for(int i=index;i<arr.length;i++){
            // Choose
            char next = queue.poll();   
            combination.add(next);
            ans.add(new ArrayList(combination));

            // Explore
            solve(index+1, arr, queue, new ArrayList(combination), ans);

            // Unchoose
            combination.remove(combination.size()-1);
            queue.add(next);
        }
    }
}

Output
1, 
1, 2, 
1, 2, 3, 
1, 3, 
1, 3, 2, 
2, 
2, 3, 
2, 3, 1, 
2, 1, 
2, 1, 3, 
3, 
3, 1, 
3, 1, 2, 
3, 2, 
3, 2, 1, 

Answer 1

I like to follow Steven Skiena's approach to backtracking outlined in his textbook 'The Algorithm Design Manual'. I'll be sourcing from his textbook in my answer, it can be easily found online.

He typically separates backtracking problems into three main functions:

is a solution(a,k,input) – This Boolean function tests whether the first k elements of vector a from a complete solution for the given problem. The last argument, input, allows us to pass general information into the routine. We can use it to specify n—the size of a target solution. This makes sense when constructing permutations or subsets of n elements, but other data may be relevant when constructing variable-sized objects such as sequences of moves in a game.

In this scenario, because we are looking for combination, every input that is passed into this function will be considered a solution. But if you were looking for all permutations, for example, then this function would check if the input is of length 3.

construct_candidates(a,k,input,c,ncandidates) – This routine fills an array c with the complete set of possible candidates for the kth position of a, given the contents of the first k − 1 positions. The number of candidates returned in this array is denoted by ncandidates. Again, input may be used to pass auxiliary information.

So for your example, assume we're passing in the array [1,2]. Then construct_candidates will return all the possibly values that could be next. In this case, the only next candidate is [3]. But if, our input is an array with 1 element, [2], then our construct_candidate would return [1,3] because the next elements for this potential solution are 1 or three. Make sense? Then whatever construct_candidate returns, will be tacked on to the input (So our next iteration of backtrack, out input will be [2,1] and [2,3] )

construct_candidates(a,k,input,c,ncandidates){
    for(int i = 1; i <= 3; i++){
        if(i is not in array input[])
            c.add(i)
    }
return c;
}

So here, our candidates will be the numbers 1 through 3, so long as the numbers don't exist in the input array, then they are a candidate. For example if our input is [3], our function should return [1,2]. If our input is empty [ ], then our function should return [1,2,3].

process solution(a,k,input) – This routine prints, counts, or however processes a complete solution once it is constructed.

In our case, we'll likely just print out the solution

Here's the psuedocode that pulls it all together:

backtrack(int a[], int k, data input)
{
int c[MAXCANDIDATES]; /* candidates for next position */
int ncandidates; /* next position candidate count */
int i; /* counter */
if (is_a_solution(a,k,input))
    process_solution(a,k,input);
else {
    k = k+1;
    construct_candidates(a,k,input,c,&ncandidates);
    for (i=0; i<ncandidates; i++) {
        a[k] = c[i];
        make_move(a,k,input);
        backtrack(a,k,input);
        unmake_move(a,k,input);
        if (finished) return; /* terminate early */
     }
}

}

Let me know if you need me to clarify anything else, I'd be happy to help. I TAed for Professor Skiena in his Algorithms class last year, so it's still fresh in my mind. I reccomend skimming his chapter on Backtracking (Chapter 7.7). It's very informative.

Source: Algorithm Design Manual by Steven Skiena Page 231-232