java - 组合和回溯编码问题

Question

给定一个不同整数候选者的数组和一个目标整数目标，返回所有候选者的唯一组合的列表，其中选择的数字总和为目标。可以从候选者中选择相同的数字无限次。组合本身必须在排序顺序并且不包含重复的组合。

组合中的元素 (a1, a2, ... , ak) 必须按非降序排列。（即，a1 ≤ a2 ≤ … ≤ ak）。

组合A > 组合B iff (a1 > b1) OR (a1 = b1 AND a2 > b2) OR ... (a1 = b1 AND a2 = b2 AND ... ai = bi AND ai+1 > bi+1)

我用 java 语言编写的以下代码使用回溯并获取所有唯一组合并将它们添加到 res 变量中。

但我无法弄清楚这些组合中的每一个将如何排序。在我看来，简单地对每个组合进行排序会增加时间复杂度。

输入：A = [2,3,6,7]，目标 = 7 输出：[[2,2,3],[7]]

通过排序，我的意思是 [3,2,2] 不能作为有效组合

  public ArrayList<ArrayList<Integer>> combinationSum(ArrayList<Integer> A, int target) {
    ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    ArrayList<Integer> comb = new ArrayList<Integer>();
    generate(0, A, target, comb, res);
    return res;
}

public static void generate(int idx, ArrayList<Integer> A, int target, ArrayList<Integer> comb, ArrayList<ArrayList<Integer>> res) {
    if(target < 0) return;
    if(target == 0) {
       res.add(new ArrayList<Integer>(comb));
       return;
    }
    for(int i=idx; i<A.size(); i++) {
        comb.add(A.get(i));
        generate(i, A, target - A.get(i), comb, res);  // backtracking step
        comb.remove(comb.size() - 1);
    }
}}

标签： javaalgorithmdata-structuresbacktrackingrecursive-backtracking