java - 编写一个算法来解决给定数字的所有可能组合的解决方案

Question

这样做的想法是，有一个可以多次使用的数字列表(如果解决方案是 5，列表是 (1, 4, 2) 那么可能的解决方案是 (1,1,1, 1,1) (1,4) (1,2,2) (4,1) (2,1,1,1) (2,1,2) (2,2,1)

我当前的代码是:

static void J5(int distance, ArrayList<Integer> p)
{
    for (int i=0; i < p.size(); i++)
    {
        int sub = (distance - p.get(i));

        if (sub == 0)
        {
            System.out.print(p.get(i) + "\n");
            return;
        }
        if (sub < 0)
        {
            sub = distance - p.get(i);      
        }
        if (sub > 0)
        {
            System.out.print(p.get(i) + " ");
            J5(sub, p);
        }
    }
}

所以本质上它是从 5 的距离中减去，并对结果使用递归。我的输出是

2 2 1
1 2
4 1
1 2 2
4

在这个例子中，几乎唯一完全正确的是第一次迭代 2 + 2 + 1 = 5，但接下来的应该是 (2,1,2)尽管每个元素都可以多次使用，但也没有 (1,1,1,1,1)。

Answer 1

在这里，我为您编写了一个简洁明了的解决方案:

public class Test {
    static void combinationSumUtils(int indx, int sum, ArrayList<Integer> candidates, ArrayList<Integer> solution) {
        if(indx == candidates.size()) {
            if(sum == 0) {
                for(int i = 0; i < solution.size(); ++i) {
                    System.out.print(solution.get(i) + " ");
                }
                System.out.println();
            }
            return;
        }
        if(sum == 0) {
            for(int i = 0; i < solution.size(); ++i) {
                System.out.print(solution.get(i) + " ");
            }
            System.out.println();
            return;
        }
        for(int i = 0; i < candidates.size(); ++i) {
            if(sum - candidates.get(i) >= 0) {
                solution.add(candidates.get(i));
                combinationSumUtils(i, sum - candidates.get(i), candidates, solution);
                solution.remove(solution.size() - 1);
            } else {
                break;
            }
        }
    }

    public static void main(String[] args) {
        ArrayList<Integer> solution = new ArrayList<Integer>();
        ArrayList<Integer> candidates = new ArrayList<Integer>();
        candidates.add(1);
        candidates.add(4);
        candidates.add(2);
        Collections.sort(candidates);
        combinationSumUtils(0, 5, candidates, solution);
    }
}

输出:

1 1 1 1 1 
1 1 1 2 
1 1 2 1 
1 2 1 1 
1 2 2 
1 4 
2 1 1 1 
2 1 2 
2 2 1 
4 1

等效的 C++ 解决方案:

void combinationSumUtils(int indx, int sum, vector<int> &candidates, vector<int> &solution, vector<vector<int> > &result) {
        if(indx == candidates.size()) {
            if(sum == 0) result.push_back(solution);
            return;
        }
        if(sum == 0) {
            result.push_back(solution);
            return;
        }
        for(int i = 0; i < candidates.size(); ++i) {
            if(sum - candidates[i] >= 0) {
                solution.push_back(candidates[i]);
                combinationSumUtils(i, sum - candidates[i], candidates, solution, result);
                solution.pop_back();
            } else {
                break;
            }
        }
    }

    vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
        vector<vector<int> > result;
        vector<int> solution;
        if(candidates.size() < 0) return result;
        sort(candidates.begin(), candidates.end());
        combinationSumUtils(0, target, candidates, solution, result);
        return result;
    }