【leetcode】含有重复元素集合的组合

0、相关算法归类

78 79 80 81 82 五道题，都属于回溯算法的应用，等把题解写完之后可以归类。

回溯算法直观介绍：

一、题目描述

给定一个可能有重复数字的整数数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次，解集不能包含重复的组合。

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

二、代码思路

乍一眼看，这就是纯纯的回溯算法，我只需要使用回溯依次搜索并判断是否选择每个元素即可。

思路是很简单的，所以，就开始写回溯算法。但是，单纯的二叉树回溯算法，只可以解决一部分问题。但是题目要求解集不能有重复的元素，而且整数数组 candidates是有重复数字的整数数组，所以我们使用二叉树回溯搜索算法，必然解集中存在重复的元素。我们要想办法去重。

如何去重呢 ？

去重往往会依靠HashMap的key唯一性来去重，所以我们的思路也很简单，使用 private HashSet set = new HashSet(); 来保证 List list 没有重复的。 但是，我们仍然需要对list进行排序，因为[1,2,3] 和 [3 , 2, 1] 这两个集合是不一样的，我们必须去重。

如何对list排序 ？

往往是使用 Collections.sort() ，可以传入比较器，也可以不传入比较器，不传入比较器会默认使用list集合元素的CompareTo方法，也就是说List集合中的元素要实现Compareable接口。

这样就成功了吗 ？

按照道理来讲，我们排序之后，再加入HashSet中，已经可以完成去重工作了，但是我发现答案并不对。其原因就是由于浅复制的问题，以及回溯算法的算法思想。

我们知道，浅复制只是复制了引用，内存空间并没有复制，所以对内存空间进行排序，两个引用其实指向的同一个地址空间。

回溯的思想是：我先选上该元素看看行不行，判断完成之后，我再把该元素删掉，从而接着判断如果不选该元素如何，从而形成一颗二叉搜索树，一般是完全二叉树，出现剪支就不是了。

其实问题就出现在这里

不能浅复制，浅复制之后，Collections排序之后，由于list 和 listCopy都指向的同一块内存区域的元素

所以，排序之后，list和listCopy所指向的同一块内存区域的元素，都会变化。变化之后，你想再删除原来最后添加的元素index，很有可能这个index位置的元素就变成其他元素了，很有可能删错。

比如[2，2，2，1]这个测试用例，原本是[2,2,1]符合条件，但是排序之后变成了[1,2,2],这是考虑选择1的情况，现在我们考虑，不选1，也就是把1删掉，但是很可惜1的位置变成了2，所以我们错误的把2删掉了。所以，我们应该使用 boolean remove(Object o) 来删除，而并非使用 E remove(int index)来删除。

三、代码思路

class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.combinationSum2(new int[] {1,2},3);
    }
    private int sum;
    private int target;
    private List<Integer> list = new LinkedList();
    //private List> res = new LinkedList();
    //进行一个去重的操作。
    private HashSet<List<Integer>> set = new HashSet();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        //经典回溯算法：
        //这道题是昨天81题的降级版本，昨天81题，每个元素可以重复被选，因此构造的回溯搜索树是多叉树
        //这道题明确指明元素不能被重复选，所以摆明了就是二叉搜索树的回溯算法。
        //回溯算法的解释：http://c.biancheng.net/view/3400.html
        this.target = target;
        dfs(candidates, 0);
        return new LinkedList(set);

    }
    public void dfs(int [] candidates, int cur) {
        //请注意！！！应该先判断sum是否等于目标值，而不是先判断cur == length
        //这样才能保证最后一个元素能够不配排除，正确的加入到集合中。
        if (sum == target) {
            //不能浅复制，浅复制之后，Collections排序之后，由于list 和 listCopy都指向的同一块内存区域的元素
            //所以，排序之后，list和listCopy所指向的同一块内存区域的元素，都会变化。
            //变化之后，你想再删除原来最后添加的元素index，很有可能这个index位置的元素就变成其他元素了，很有可能删错
            //比如[2，2，2，1]这个测试用例，原本是[2,2,1]符合条件，但是排序之后变成了[1,2,2],这是考虑选择1的情况，现在我们考虑
            //不选1，也就是把1删掉，但是很可惜1的位置变成了2，所以我们错误的把2删掉了。
            List<Integer> listCopy = list;
            Collections.sort(listCopy);
            set.add(new LinkedList(listCopy));
            return;
        }
        if (cur > candidates.length - 1) {
            return;
        }
        //进行一下剪支操作
        if (sum > target) {
            return;
        }
        //假如选上该元素
        sum += candidates[cur];
        list.add(candidates[cur]);
        //接着判断是否选下一个元素
        dfs(candidates, cur + 1);
        //不选该元素的情况
        sum -= candidates[cur];
        //List 接口只有remove(Object) 方法
        list.remove(new Integer(candidates[cur]));
        //接着判断下一个元素
        dfs(candidates, cur + 1);
        //如此就能构成一颗二叉树，树的每一条路径，都代表一种选择结果
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56