摘要：深度優(yōu)先搜索復雜度時間空間遞歸棧空間思路因為我們可以任意組合任意多個數(shù)，看其和是否是目標數(shù)，而且還要返回所有可能的組合，所以我們必須遍歷所有可能性才能求解。這題是非常基本且典型的深度優(yōu)先搜索并返回路徑的題。本質(zhì)上是有限深度優(yōu)先搜索。

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
Note: All numbers (including target) will be positive integers. Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak). The solution set must not contain duplicate combinations. For example, given candidate set 2,3,6,7 and target 7,  A solution set is:
[7] 
[2, 2, 3]

時間 O(N!) 空間 O(N) 遞歸棧空間

因為我們可以任意組合任意多個數(shù)，看其和是否是目標數(shù)，而且還要返回所有可能的組合，所以我們必須遍歷所有可能性才能求解。為了避免重復遍歷，我們搜索的時候只搜索當前或之后的數(shù)，而不再搜索前面的數(shù)。因為我們先將較小的數(shù)計算完，所以到較大的數(shù)時我們就不用再考慮有較小的數(shù)的情況了。這題是非常基本且典型的深度優(yōu)先搜索并返回路徑的題。本題需要先排序，不然過不了Leetcode。

要先問清楚什么樣的組合是有效的，比如該題，是可以連續(xù)選擇同一個數(shù)加入組合的。

public class Solution {
    
    List> res;
    
    public List> combinationSum(int[] candidates, int target) {
        res = new LinkedList>();
        List tmp = new LinkedList();
        // 先將數(shù)組排序避免重復搜素
        Arrays.sort(candidates);
        helper(candidates, target, 0, tmp);
        return res;
    }
    
    private void helper(int[] nums, int target, int index, List tmp){
        // 如果當前和已經(jīng)大于目標，說明該路徑錯誤 
        if(target < 0){
            return;
        // 如果當前和等于目標，說明這是一條正確路徑，記錄該路徑
        } else if(target == 0){
            List oneComb = new LinkedList(tmp);
            res.add(oneComb);
        // 否則，對剩余所有可能性進行深度優(yōu)先搜索
        } else {
            // 選取之后的每個數(shù)字都是一種可能性
            for(int i = index; i < nums.length; i++){
                // 典型的先加入元素，再進行搜索，遞歸回來再移出元素的DFS解法 
                tmp.add(nums[i]);
                helper(nums, target - nums[i], i, tmp);
                tmp.remove(tmp.size() - 1);
            }
        }
    }
}

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
Note: All numbers (including target) will be positive integers.
Elements in a combination (a1, a2, … , ak) must be in non-descending
order. (ie, a1 ≤ a2 ≤ … ≤ ak). The solution set must not contain
duplicate combinations. For example, given candidate set
10,1,2,7,6,1,5 and target 8,  A solution set is:
[1, 7] 
[1, 2, 5] 
[2, 6] 
[1, 1, 6]

時間 O(N!) 空間 O(N) 遞歸棧空間

這題和I的區(qū)別在于同一個數(shù)只能取一次，比如數(shù)組中只有3個1，那結(jié)果中也最多只有3個1，而且結(jié)果也不能重復。所以我們在遞歸時首先要把下標加1，這樣下輪搜索中就排除了自己。其次，對一個數(shù)完成了全部深度優(yōu)先搜索后，比如對1完成了搜索，那么我們要把后面的1都跳過去。當然，跳過只是針對本輪搜索的，在對第一個1的下一輪的搜索中，我們還是可以加上第二個1。只是我們不能再以第二個1開頭了而已。為了能連續(xù)跳過重復的數(shù)，這里我們必須先排序。

public class Solution {
    
    List> res;
    
    public List> combinationSum2(int[] candidates, int target) {
        res = new LinkedList>();
        List tmp = new LinkedList();
        Arrays.sort(candidates);
        helper(candidates, target, 0, tmp);
        return res;
    }
    
    private void helper(int[] nums, int target, int index, List tmp){
        if(target < 0){
            return;
        } else if(target == 0){
            List oneComb = new LinkedList(tmp);
            res.add(oneComb);
        } else {
            for(int i = index; i < nums.length; i++){
                tmp.add(nums[i]);
                // 遞歸時下標加1
                helper(nums, target - nums[i], i+1, tmp);
                tmp.remove(tmp.size() - 1);
                // 跳過本輪剩余的重復元素
                while(i < nums.length - 1 && nums[i] == nums[i + 1]){
                    i++;
                }
            }
        }
    }
}

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.
Ensure that numbers within the set are sorted in ascending order.
Example 1:
Input: k = 3, n = 7

Output:
[[1,2,4]]

Example 2:
Input: k = 3, n = 9

Output:
[[1,2,6], [1,3,5], [2,3,4]]

時間 O(9!) 空間 O(9) 遞歸棧空間

這題其實是II的簡化版，設想一個[1,2,3,4,5,6,7,8,9]的數(shù)組，同樣一個元素只能取一次，但是已經(jīng)預先確定沒有重復了。所以可以省去跳過重復元素的部分。不過，我們在遞歸的時候要加一個額外的變量k來控制遞歸的深度，一旦超過了預設深度，就停止該分支的搜索。本質(zhì)上是有限深度優(yōu)先搜索。

public class Solution {
    
    List> res;
    
    public List> combinationSum3(int k, int n) {
        res = new LinkedList>();
        List tmp = new LinkedList();
        helper(k, n, 1, tmp);
        return res;
    }
    
    private void helper(int k, int target, int i, List tmp){
        if(target < 0 || k < 0){
            return;
        } else if (target == 0 && k == 0){
            List oneComb = new LinkedList(tmp);
            res.add(oneComb);
        } else {
            for(int j = i; j <= 9; j++){
                tmp.add(j);
                helper(k-1, target-j, j+1, tmp);
                tmp.remove(tmp.size() - 1);
            }
        }
    }
}