如何使用回溯生成给定元素数组的所有组合？

Question

给定一个数组，生成所有组合

例如：

输入：{1,2,3}

输出：{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}

我正在练习回溯算法，我想我了解回溯的一般概念。你本质上就是运行一个DFS去寻找满足一个条件的路径。如果命中不满足条件的节点，则退出当前节点，从上一个节点开始。

但是，我无法理解如何实现隐式树的遍历部分。

我最初的想法是沿着最左边的路径遍历，这将给我 {1}、{1,2}、{1,2,3}。但是，一旦我回溯到 1，我如何继续添加 3 以获得 {1,3} 和 {1,3,2} 之后？即使我有 2 个指针，我也需要它指向 2 才能最终获得 {1,3,2}。

我应该采取什么步骤来解决这样的回溯问题？

感谢大家的回复。这是我想出的算法。

    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

我喜欢遵循 Steven Skiena 在他的教科书中概述的回溯方法 'The Algorithm Design Manual'。我将在我的回答中从他的教科书中采购，它可以很容易地在网上找到。

他通常将回溯问题分为三个主要功能：

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.

在这种情况下，因为我们正在寻找组合，所以传递给此函数的每个输入都将被视为一个解决方案。但是，例如，如果您正在寻找所有排列，那么此函数将检查输入的长度是否为 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.

因此，对于您的示例，假设我们传入数组 [1,2]。然后 construct_candidates 将 return 所有下一个可能的值。在这种情况下，唯一的下一个候选者是 [3]。但是，如果我们的输入是一个包含 1 个元素 [2] 的数组，那么我们的 construct_candidate 将 return [1,3] 因为此潜在解决方案的下一个元素是 1 或 3。说得通？然后无论 construct_candidate returns，将被附加到输入（因此我们的下一次回溯迭代，输出输入将是 [2,1] 和 [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;
}

所以在这里，我们的候选项将是数字 1 到 3，只要输入数组中不存在这些数字，它们就是候选项。例如，如果我们的输入是 [3]，我们的函数应该 return [1,2]。如果我们的输入为空 [ ]，那么我们的函数应该 return [1,2,3].

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

在我们的例子中，我们可能只是打印出解决方案

这是将它们组合在一起的伪代码：

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 */
     }
}

}

如果您需要我澄清任何其他问题，请告诉我，我很乐意提供帮助。去年我在 Skiena 教授的算法 class 上担任 TA，所以它在我脑海中仍然记忆犹新。我建议浏览一下他关于回溯的章节（第 7.7 章）。信息量很大。

来源：Steven Skiena 的算法设计手册第 231-232 页

如何使用回溯生成给定元素数组的所有组合？

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

algorithm

combinations

permutation

backtracking