LeetCode 子集合，排列组合，回文分离等问题的通用递归算法

摘要：通用算法思路总结初始结果列表。可能要将数集排序，方便处理重复元素的情况。书写递归函数，先要考虑原点状况，一般就是考虑什么情况下要将当前结果添加到结果列表中。每当一个元素添加到当前结果中之后，要再调用递归函数，相当于固定了前缀穷举后面的变化。

通用算法思路总结：

初始结果列表。

可能要将数集排序，方便处理重复元素的情况。

调用递归函数。

书写递归函数，先要考虑原点状况，一般就是考虑什么情况下要将当前结果添加到结果列表中。

for循环遍历给定集合所有元素，不同题目区别在于进行循环的条件，具体看例子。每当一个元素添加到当前结果中之后，要再调用递归函数，相当于固定了前缀穷举后面的变化。

调用完之后要将当前结果中最后一个元素去掉，进行下一个循环才不会重复。

如果对于递归过程不熟悉的，可以用debug模式观察参数在递归过程中的变化。

举例包含：

78.Subsets

90.SubsetsII

46.Permuation

77.Combinations

39.Combination Sum

40.Combination Sum II

131.Panlindrome Partitioning

给一个数集（无重复数字），要求列出所有子集。

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);
        }

    }
}

给一个数集（有重复数字），要求列出所有子集。

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);
    }
} 

给一个数集（无重复元素），返回所有排列。

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
给一个正整数n,要求返回1-n中k（k<=n）个数所有组合的可能。
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
给一个数集和一个数字target，要求返回 用数集中数字加和等于target的所有组合 （数集中的数可以重复使用）。
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，因为可以重复使用元素
                    helper(candidates,temp,tempRemain,i);
                    temp.remove(temp.size()-1);
                }
            }
        
    }
}


40.Combination Sum II
给一个数集和一个数字target，要求返回 用数集中数字加和等于target的所有组合 （数集中的数不可以重复使用）。
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判断条件，跳过不必要的循环。
        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
给定一个回文字符串，要求将其分成多个子字符串，使得每个子字符串都是回文字符串，列出所有划分可能。
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;
    }
}

如有错误，欢迎指出。
ref: general approach for ... problem