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

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 = 7My 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 ) {

    Collections.sort(temp); // This will sort your list, that you want to add

    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.

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

    return;

}

或者您也可以在列表中按排序顺序添加元素res，然后使用 HashSet 从res列表中删除重复项。

 Set<List<Integer>> set = new HashSet<>(res);

 res.clear();

 res.addAll(set);

Answer 2

完全避免重复（无需显式检查）的一种可能的替代方法如下：

与其遍历辅助函数中 for 循环中的每个元素（请注意，索引参数在递归调用中始终相同），不如考虑如下解决方案：

1. 您要么考虑给定索引处的元素，然后使用相同的索引再次递归（因此能够多次考虑相同的元素）或

2. 你不考虑当前元素，用index+1递归。

这样你就不会在你的解决方案中得到重复项。

不在这里发布整个解决方案（不想让你失去所有的乐趣 :P ），但辅助函数中的递归步骤基本上是：

# don't consider element at index, and increment index in recursive call

self.helper(candidates, target, index+1, res, temp) 

# consider element at index `index`

self.helper(candidates, target-candidates[index], index, res, temp+[candidates[index]])    

Answer 3

我不确定最好的意思是什么，但你可以使用Collection.sort和Set

public 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) {

    if (a1.length != a2.length) {

        return false;

    }

    Arrays.sort(a1);

    Arrays.sort(a2);

    for (int i = 0; i < a1.length; i++) {

        if (a1[i] != a2[i]) {

            return false;

        }

    }

    return true;

}

将此应用于您的结果并保留返回的数组结果false。