40 组合总和 II

题目：

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

说明：

• 所有数字（包括目标数）都是正整数。
• 解集不能包含重复的组合。

示例：

• 示例1

输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]

• 示例2

输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
[1,2,2],
[5]
]

解题思路

1. 首先组合总和问题想到用递归的方式求解，定义递归函数为dfs(pos, rest)，其中pos表示我们当前递归到了数组 candidates[]中的第pos个数，而rest表示我们还需要选择和为rest的数放入列表作为一个组合。
 对于数组candidates[]中的每个元素，都有两种选择方式，要么选，要么不选。如果选择candidates[pos]，那么递归子过程是dfs(pos + 1, rest - candidates[pos])，当然，必须满足rest >= candidates[pos]。如果不选，则递归子过程是dfs(pos + 1, rest)。
 在每次的递归开始前，如果rest==0,说明target的组合已经找到，将组合放入答案中。每次调用递归函数前，如果我们选择了那个数，就需要将其放入到列表的末尾，该列表存储了我们选择的所有的数。在回溯时，如果我们选择了那个数，就要将其从列表的末尾删除。
注：本题的解集不能包含重复的组合，上述算法能去除重复解，比如candidates = [1,1]，target = 1，那么就会将两个1放入解集中
2. 因此在求出组合时，要增加去重操作。将相同的数一起处理，将从candidates[]中拿数据改为从一个map(数，出现次数)中去拿数据，这样就不会出现重复的解集。

代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * 组合总和2
 */
public class CombinationSum2 {

    /**
     * candidates中每个数出现的次数
     */
    List<int[]> freq = new ArrayList<int[]>();

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

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

    /**
     * 组合总和2
     * @param candidates
     * @param target
     * @return
     */
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {

        //从小到大排序，递归时会选择小的数，再选择大的数，如果选择的数已经大于rest，后面的数就减掉了
        Arrays.sort(candidates);
        for (int num : candidates){
            int size = freq.size();
            //排序以后 如果是相同的就加次数 不相同就加数，次数为1
            if (freq.isEmpty() || num != freq.get(size - 1)[0]){
                freq.add(new int[]{num, 1});
            }else {
                ++freq.get(size - 1)[1];
            }
        }
        dfs(0, target);
        return ans;
    }

    /**
     * 从0位置开始，看余下的数
     */
    public void dfs(int pos, int rest){
        //如果余下的数为0，说明正好凑好
        if (rest == 0){
            ans.add(new ArrayList<Integer>(sequence));
        }
        //如果走到了最后一位，或者走到的位置已经大于了rest，直接返回
        if (pos == freq.size() || rest < freq.get(pos)[0]){
            return;
        }
        //不选
        dfs(pos+1, rest);

        int most = Math.min(rest / freq.get(pos)[0], freq.get(pos)[1]);
        for (int i=1; i<=most; ++i){

            sequence.add(freq.get(pos)[0]);
            //选
            dfs(pos+1, rest - i * freq.get(pos)[0]);
        }
        //将选择的数从列表中删除
        for (int i=1; i<=most; ++i){
            sequence.remove(sequence.size() - 1);
        }
    }
}