在以下情况下检查重复答案的有效方法是什么？

Question

public List<List<Integer>> combinationSum(int[] candidates, int target) 

{

    List<List<Integer>> res = new ArrayList<>();

    Arrays.sort(candidates);        

    helper(candidates, target, res, new ArrayList<>(), 0);        

    return res;

} 

private void helper (int[] candidates, int target, List<List<Integer>> res, List<Integer> temp, int index) {

    if( target < 0) return;

    if(target == 0) {

        res.add(new ArrayList<>(temp));

        return;

    }

    for(int i = index; i < candidates.length; i++) {

        if(candidates[i] > target) {

            return;

        }

        temp.add(candidates[i]);

        helper(candidates, target - candidates[i], res, temp, index);

        temp.remove(temp.size() - 1);

    }

}

For an input: candidates = [2,3,6,7], and target = 7

My output is: [[2,2,3],[2,3,2],[3,2,2],[7]]

Correct Output: [[2,2,3],[7]]

显然，我需要在添加到结果之前检查重复项。

我知道我可以创建一组字符串，其中每个字符串都是列表的排序版本，例如 [2,3,2] => &ldquo;223&rdquo;。这将帮助我检查是否需要将列表添加到结果中。

我的问题是在我的情况下检查重复项的最佳方法是什么？

Answer 1

通过在您的辅助方法中添加以下行，可以达到预期的结果。if(target == 0 ) {&nbsp; &nbsp; Collections.sort(temp); // This will sort your list, that you want to add&nbsp; &nbsp; if(!res.contains(temp)) // Check if sorted list already existing in your result list or not. Only add the temp list if it does not exist in your res list.&nbsp; &nbsp; &nbsp; &nbsp; res.add(new ArrayList<>(temp));&nbsp; &nbsp; return;}或者您也可以在列表中按排序顺序添加元素res，然后使用 HashSet 从res列表中删除重复项。&nbsp;Set<List<Integer>> set = new HashSet<>(res);&nbsp;res.clear();&nbsp;res.addAll(set);

Answer 2

完全避免重复（无需显式检查）的一种可能的替代方法如下：与其遍历辅助函数中 for 循环中的每个元素（请注意，索引参数在递归调用中始终相同），不如考虑如下解决方案：您要么考虑给定索引处的元素，然后使用相同的索引再次递归（因此能够多次考虑相同的元素）或你不考虑当前元素，用index+1递归。这样你就不会在你的解决方案中得到重复项。不在这里发布整个解决方案（不想让你失去所有的乐趣 :P ），但辅助函数中的递归步骤基本上是：# don't consider element at index, and increment index in recursive callself.helper(candidates, target, index+1, res, temp)&nbsp;# consider element at index `index`self.helper(candidates, target-candidates[index], index, res, temp+[candidates[index]])&nbsp; &nbsp;&nbsp;

Answer 3

我不确定最好的意思是什么，但你可以使用Collection.sort和Setpublic static Set<List<Integer>> combinationSum(int[] candidates, int target){--->>    Set<List<Integer>> res = new HashSet<>();    Arrays.sort(candidates);    helper(candidates, target, res, new ArrayList<>(), 0);    return res;}private static void helper(int[] candidates, int target, Set<List<Integer>> res, List<Integer> temp, int index) {    if( target < 0) return;    if(target == 0) {        ArrayList<Integer> newRes = new ArrayList<>(temp);--->>        Collections.sort(newRes);        res.add(newRes);        return;    }    for(int i = index; i < candidates.length; i++) {        if(candidates[i] > target) {            return;        }        temp.add(candidates[i]);        helper(candidates, target - candidates[i], res, temp, index);        temp.remove(temp.size() - 1);    }}输入候选人 = [2,3,6,7]，目标 = 7输出[[2, 2, 3], [7]]

Answer 4

你不一定需要为此设置。您可以使用然后检查所有索引是否相等来对两个数组进行排序Arrays.sort()，例如：public Boolean isEqual(int[] a1, int[] a2) {&nbsp; &nbsp; if (a1.length != a2.length) {&nbsp; &nbsp; &nbsp; &nbsp; return false;&nbsp; &nbsp; }&nbsp; &nbsp; Arrays.sort(a1);&nbsp; &nbsp; Arrays.sort(a2);&nbsp; &nbsp; for (int i = 0; i < a1.length; i++) {&nbsp; &nbsp; &nbsp; &nbsp; if (a1[i] != a2[i]) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return false;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return true;}将此应用于您的结果并保留返回的数组结果false。