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

Question

我正在尝试在 leetcode 中解决这个问题：https://leetcode.com/problems/combination-sum/

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] => "223"。这将帮助我检查是否需要将列表添加到结果中。

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

Answer 1

您不一定需要 Set。您可以改为使用 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;
}

将此应用于您的结果并保留 return false.

的数组结果

Answer 2

我不确定 best 是什么意思，但是你可以使用 Collection.sort and 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 3

通过在您的辅助方法中添加以下几行即可达到预期的结果。

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 4

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

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

要么考虑给定索引处的元素，然后使用相同的索引再次递归（因此能够多次考虑相同的元素）或
不考虑当前元素，用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]])

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

What would be an efficient way to check duplicate answer in the following case?

java

arrays

hashset