java - 如何避免 Java 中 List> 中的重复列表

Question

这样，[2,2,3] 和 [2,3,2] 都不应该出现在其中。

我在代码中所做的事情是给定一组 [2, 3, 6, 7] 和目标 7，我找到了候选数字总和达到目标的独特组合

输出:

[

[7]，

[2,2,3]

]该代码工作正常，但我觉得我通过创建 HashSet<ArrayList<Integer>> 使用了一种复杂的方式，使用 Collection.sort() 来避免重复列表。有没有更好的方法可以避免这种情况？

 HashSet<ArrayList<Integer>> set= new HashSet<ArrayList<Integer>>();
        public List<List<Integer>> combinationSum(int[] candidates, int target) {        
            backtract(candidates,target,0, new ArrayList<Integer>(),0);   

            List<List<Integer>> output=new ArrayList<List<Integer>>(set);
            return output;
        }



 public void backtract(int[] candidates, int target, int pos, List<Integer> list, int sum){
        if(sum==target){
            ArrayList l=new ArrayList<Integer>(list);     

            Collections.sort(l);
            set.add(l);
         }

    for(int i=0;i<candidates.length;i++){
        if(sum+candidates[i] > target){
            continue;
        }
        sum=sum+candidates[i];           
        list.add(candidates[i]);
        backtract(candidates,target,i+1, list,sum);
        list.remove(new Integer(candidates[i]));
        sum=sum-candidates[i];
    }
}

Answer 1

这是一种可能的方法。

public static void backtract(int[] candidates, int target, int pos, List<Integer> list, int sum) {
    if(sum == target){
        finalOutput.add(new ArrayList<Integer>(list));
        return;
    }

    for (int i = pos; i < candidates.length; i++) {
        for (int j = 1; j <= (target - sum) / candidates[i]; j++) {
            List<Integer> newList = new ArrayList<>(list);
            for (int k = 0; k < j; k++) {
                newList.add(candidates[i]);
            }
            backtract(candidates, target, i + 1, newList, sum + (candidates[i] * j));
        }
    }
}

这个问题的主要挑战是允许多次拾取特定元素。

因此，(在上面的代码中)的想法是在每次递归调用上继续前进。在您的代码中，每个递归调用都从索引 0 处的元素开始，这就是导致重复的原因。在这里，每个递归调用都从索引 pos 处的元素开始。

要多次选择某个特定元素，我们通过检查(target - sum)/Candidates[i](令其为ct)来检查其中有多少(当前元素)可以对总体(剩余)目标做出贡献。因此，我们通过选择其中的 1, 2, 3... ct 来进行递归调用(添加到当前总和中)。

几点:

1. 为了避免改变数组，我创建了新的数组来简化代码。如果它被证明会影响性能，您可以更改它。
2. 我将finalOutput保留为静态变量。您可以将其作为参数传递。