[Leetcode] Combination VS Subset

在Leetcode上，有两个非常类似的题目，Combination系列（Combination，Combination Sum，Combination Sum II）和Subset系列（Subset，Subset II），这两个系列的题都是使用DFS的思路来做的题，而且可以互通。我最一开始的方法是纯粹的暴力枚举方法，思路是这样的：

首先将数组排序，这一步可以使得一方面结果满足增序，一方面相同元素互相在一起，方便之后的排除。对于每一个元素，我们有两种选择，选或者不选，因此我们可以用DFS递归的枚举每一种可能，然后加入答案。然而这种方法的问题是，去除重复比较的隐晦，不是很直接，很容易写错。

之后看到的另一种思路，按照子问题的方法来想（我上面的应该算是暴力枚举），比如对于Combination，当我们现在的情况是数组[2, 3, 5, 6]，我们应该如何想？我们可以想成我现在选一个数，然后再带上子问题的Combination的结果，就组成了一个答案。比如我现在选择了2，那么我只要知道子问题数组[3, 5, 6]的组合情况就可以了，但是我现在可以不选择2，我选择了3，那么我就找子问题[5, 6]的组合情况。也就是说，我们在这一步需要枚举子问题的情况。同时，我们需要在每次递归的开始，对当前解进行判断，是否满足条件，加入解集中。因此，整体的结构就成了：

1. 判断当前解
2. 根据当前情况，枚举子问题

这样，在去除重复的时候非常容易，之所以会有重复解是因为这种情况：

比如我们当前的数组是1，1，2，XXXXXX，那么我们首先枚举选择1的子问题，当子问题返回了之后，我们如果再次选择第二个1，就会产生重复，起重复的情况是选择1的子问题之后（数组[1, 2, XXXXXX]）再次选择2的子问题。如何避免重复，我们只需要跳过重复的元素就可以了。

按照上面这种枚举子问题的思路来写，这种系列的题就非常容易写了，比我原来暴力枚举的思路容易很多，去重也非常的容易。

    public void subsets(int[] S, int beg, List<Integer> array, List<List<Integer>> result) {
        result.add(new ArrayList<Integer>(array));
        for(int i = beg; i < S.length; i++) {
            if(i > beg && S[i] == S[i-1]) continue; // jump duplicate
            array.add(S[i]);
            subsets(S, i+1, array, result);
            array.remove(array.size() - 1);
        }
    }

    private void dfs(int[] num, int current, int beg, List<Integer> list, List<List<Integer>> result) {
        if(current < 0) return ;
        else if(current == 0) {
            result.add(new ArrayList<Integer>(list));
        }
        else {
            for(int i = beg; i < num.length; i++) {
                if(i > beg && num[i] == num[i-1]) continue;
                list.add(num[i]);
                dfs(num, current-num[i], i, list, result);
                list.remove(list.size() - 1);
            }
        }
    }