摘要：通用算法思路總結(jié)初始結(jié)果列表。可能要將數(shù)集排序，方便處理重復(fù)元素的情況。書寫遞歸函數(shù)，先要考慮原點(diǎn)狀況，一般就是考慮什么情況下要將當(dāng)前結(jié)果添加到結(jié)果列表中。每當(dāng)一個(gè)元素添加到當(dāng)前結(jié)果中之后，要再調(diào)用遞歸函數(shù)，相當(dāng)于固定了前綴窮舉后面的變化。

通用算法思路總結(jié)：

初始結(jié)果列表。

可能要將數(shù)集排序，方便處理重復(fù)元素的情況。

調(diào)用遞歸函數(shù)。

書寫遞歸函數(shù)，先要考慮原點(diǎn)狀況，一般就是考慮什么情況下要將當(dāng)前結(jié)果添加到結(jié)果列表中。

for循環(huán)遍歷給定集合所有元素，不同題目區(qū)別在于進(jìn)行循環(huán)的條件，具體看例子。每當(dāng)一個(gè)元素添加到當(dāng)前結(jié)果中之后，要再調(diào)用遞歸函數(shù)，相當(dāng)于固定了前綴窮舉后面的變化。

調(diào)用完之后要將當(dāng)前結(jié)果中最后一個(gè)元素去掉，進(jìn)行下一個(gè)循環(huán)才不會(huì)重復(fù)。

如果對(duì)于遞歸過程不熟悉的，可以用debug模式觀察參數(shù)在遞歸過程中的變化。

舉例包含：

78.Subsets

90.SubsetsII

46.Permuation

77.Combinations

39.Combination Sum

40.Combination Sum II

131.Panlindrome Partitioning

給一個(gè)數(shù)集（無重復(fù)數(shù)字），要求列出所有子集。

public class Solution {
    List> res;
    public List> subsets(int[] nums) {
        res = new ArrayList<>();
        if(nums.length == 0)
            return res;
        List temp = new ArrayList<>();
        helper(nums,temp,0);
        return res;

    }

    private void helper(int[] nums, List temp,int i) {
        res.add(new ArrayList<>(temp));

        for(int n = i; n < nums.length;n++){
            temp.add(nums[n]);
            helper(nums,temp,n+1);
            temp.remove(temp.size()-1);
        }

    }
}

給一個(gè)數(shù)集（有重復(fù)數(shù)字），要求列出所有子集。

public List> subsetsWithDup(int[] nums) {
    List> list = new ArrayList<>();
    Arrays.sort(nums);
    helper(list, new ArrayList<>(), nums, 0);
    return list;
}

private void helper(List> list, List tempList, int [] nums, int start){
    list.add(new ArrayList<>(tempList));
    for(int i = start; i < nums.length; i++){
        if(i > start && nums[i] == nums[i-1]) continue; // skip duplicates
        tempList.add(nums[i]);
        helper(list, tempList, nums, i + 1);
        tempList.remove(tempList.size() - 1);
    }
} 

給一個(gè)數(shù)集（無重復(fù)元素），返回所有排列。

public class Solution {
    List> result;
    public List> permute(int[] nums) {
        result = new ArrayList<>();
        if(nums.length == 0) return result;
        helper(nums,new ArrayList<>());
        return result;
    }
    
    private void helper(int[] nums,List temp){
        if(temp.size() == nums.length)
            result.add(new ArrayList<>(temp));
        else{
            for(int i = 0;i

77.Combinations
給一個(gè)正整數(shù)n,要求返回1-n中k（k<=n）個(gè)數(shù)所有組合的可能。
public class Solution {
    List> ret;
    public List> combine(int n, int k) {
        ret = new ArrayList<>();
        if(n temp = new ArrayList<>();
        helper(start,n,k,temp);
        return ret;
    }
    
    private void helper(int start,int n,int k,List temp){
        if(temp.size() == k){
            ret.add(new ArrayList(temp));
        } else {
            for(int i = start;i<=n;i++){
                temp.add(i);
                helper(i+1,n,k,temp);
                temp.remove(temp.size()-1);
            }
        }
        
    }
}


39.Combination Sum
給一個(gè)數(shù)集和一個(gè)數(shù)字target，要求返回 用數(shù)集中數(shù)字加和等于target的所有組合 （數(shù)集中的數(shù)可以重復(fù)使用）。
public class Solution {
    List> result;
    public List> combinationSum(int[] candidates, int target) {
        result = new ArrayList<>();
        Arrays.sort(candidates);
        helper(candidates,new ArrayList<>(),target,0);
        return result;
    }
    
    private void helper(int[] candidates,List temp, int remain,int start){
        if(remain == 0) {
            result.add(new ArrayList<>(temp));
            return;
        }
        
        for(int i = start;i < candidates.length && remain >= candidates[i];i++){
                int tempRemain = remain - candidates[i];
                if(tempRemain == 0 || tempRemain >= candidates[i]){
                    temp.add(candidates[i]);
                    
                    //此處用i，因?yàn)榭梢灾貜?fù)使用元素
                    helper(candidates,temp,tempRemain,i);
                    temp.remove(temp.size()-1);
                }
            }
        
    }
}


40.Combination Sum II
給一個(gè)數(shù)集和一個(gè)數(shù)字target，要求返回 用數(shù)集中數(shù)字加和等于target的所有組合 （數(shù)集中的數(shù)不可以重復(fù)使用）。
public class Solution {
    List> result;
    public List> combinationSum2(int[] candidates, int target) {
        result = new ArrayList<>();
        Arrays.sort(candidates);
        helper(candidates,new ArrayList<>(),0,target);
        return result;
    }
    
    private void helper(int[] candidates, List temp,int start ,int remain){
        if(remain == 0){
            result.add(new ArrayList<>(temp));
            return;
        }
        //加入remain判斷條件，跳過不必要的循環(huán)。
        for(int i = start; i < candidates.length && remain >= candidates[i];i++){
            if(i > start && candidates[i] == candidates[i-1]) continue;
            int tempRemain = remain - candidates[i];
            if(tempRemain == 0 || tempRemain >= candidates[i]){
                temp.add(candidates[i]);
                helper(candidates,temp,i+1,tempRemain);
                temp.remove(temp.size()-1);
            }
        }
    }
}


131.Panlindrome Partitioning
給定一個(gè)回文字符串，要求將其分成多個(gè)子字符串，使得每個(gè)子字符串都是回文字符串，列出所有劃分可能。
public class Solution {
    List> result;
    public List> partition(String s) {
        result = new ArrayList<>();
        helper(new ArrayList<>(),s,0);
        return result;
    }
    
    private void helper(List temp, String s, int start){
        if(start == s.length()){
            result.add(new ArrayList<>(temp));
            return;
        }
        for(int i = start; i < s.length();i++){
            if(isPanlidrome(s,start,i)){
                temp.add(s.substring(start,i+1));
                helper(temp,s,i+1);
                temp.remove(temp.size()-1);
            }
        }
    }
    
    private boolean isPanlidrome(String s, int low ,int high){
        while(low < high)
            if(s.charAt(low++) != s.charAt(high--)) return false;
        return true;
    }
}

如有錯(cuò)誤，歡迎指出。
ref: general approach for ... problem