題目：

給定一個數(shù)組 candidates 和一個目標數(shù) target ，找出 candidates 中所有可以使數(shù)字和為 target 的組合。

說明：

• 所有數(shù)字（包括目標數(shù)）都是正整數(shù)。
• 解集不能包含重復的組合。

示例：

• 示例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. 首先組合總和問題想到用遞歸的方式求解，定義遞歸函數(shù)為dfs(pos, rest)，其中pos表示我們當前遞歸到了數(shù)組 candidates[]中的第pos個數(shù)缕允，而rest表示我們還需要選擇和為rest的數(shù)放入列表作為一個組合。
?對于數(shù)組candidates[]中的每個元素蹭越，都有兩種選擇方式障本，要么選，要么不選响鹃。如果選擇candidates[pos]驾霜，那么遞歸子過程是dfs(pos + 1, rest - candidates[pos])，當然买置，必須滿足rest >= candidates[pos]粪糙。如果不選，則遞歸子過程是dfs(pos + 1, rest)忿项。
?在每次的遞歸開始前蓉冈，如果rest==0,說明target的組合已經(jīng)找到，將組合放入答案中轩触。每次調用遞歸函數(shù)前寞酿，如果我們選擇了那個數(shù)，就需要將其放入到列表的末尾脱柱，該列表存儲了我們選擇的所有的數(shù)伐弹。在回溯時，如果我們選擇了那個數(shù)榨为，就要將其從列表的末尾刪除惨好。
注：本題的解集不能包含重復的組合煌茴，上述算法能去除重復解，比如candidates = [1,1]日川，target = 1蔓腐，那么就會將兩個1放入解集中
2. 因此在求出組合時，要增加去重操作逗鸣。將相同的數(shù)一起處理合住，將從candidates[]中拿數(shù)據(jù)改為從一個map(數(shù)绰精，出現(xiàn)次數(shù))中去拿數(shù)據(jù)撒璧，這樣就不會出現(xiàn)重復的解集。

代碼

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

/**
 * 組合總和2
 */
public class CombinationSum2 {

    /**
     * candidates中每個數(shù)出現(xiàn)的次數(shù)
     */
    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) {

        //從小到大排序笨使，遞歸時會選擇小的數(shù)卿樱，再選擇大的數(shù)，如果選擇的數(shù)已經(jīng)大于rest硫椰，后面的數(shù)就減掉了
        Arrays.sort(candidates);
        for (int num : candidates){
            int size = freq.size();
            //排序以后 如果是相同的就加次數(shù) 不相同就加數(shù)繁调，次數(shù)為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位置開始，看余下的數(shù)
     */
    public void dfs(int pos, int rest){
        //如果余下的數(shù)為0靶草，說明正好湊好
        if (rest == 0){
            ans.add(new ArrayList<Integer>(sequence));
        }
        //如果走到了最后一位蹄胰，或者走到的位置已經(jīng)大于了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]);
        }
        //將選擇的數(shù)從列表中刪除
        for (int i=1; i<=most; ++i){
            sequence.remove(sequence.size() - 1);
        }
    }
}