子集

class Solution {
public:
    vector<vector<int>> res;
    
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<int> sub;
        backtrack(nums,0,sub);
        return res;
    }
    
    void backtrack(vector<int>& nums, int start, vector<int>& sub){
        res.push_back(sub);
        for(int i=start;i<nums.size();i++){ //从start开始
            sub.push_back(nums[i]); 
            backtrack(nums,i+1,sub);
            sub.pop_back();
        }
    }
};

 

子集II (去重复数字)

class Solution {
public:
    vector<vector<int>> res;
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<int> sub;
        sort(nums.begin(),nums.end());
        backtrack(nums,0,sub);
        return res;
    }
    
    void backtrack(vector<int>& nums, int start, vector<int>& sub){
        res.push_back(sub);
        for(int i=start;i<nums.size();i++){ //从start开始
            if(i>start && nums[i]==nums[i-1]) continue; // 如果下一个和上一个是同一个数
            sub.push_back(nums[i]); 
            backtrack(nums,i+1,sub);
            sub.pop_back();
        }
    }
};

 

全排列

class Solution {
public:
    vector<vector<int>> res;
    vector<vector<int>> permute(vector<int>& nums) {
        int len = nums.size();
        vector<int> sub;
        backtrack(nums,len,sub,0);
        return res;
    }
    
    void backtrack(vector<int>& nums, int len, vector<int>& sub, int start){
        if(sub.size()==len){
            res.push_back(sub);
            return;
        }
        
        for(int i=0;i<len;i++){ // 因为不是子集，所以必须所有数字都枚举
            if(find(sub.begin(),sub.end(),nums[i])!=sub.end()) // 如果再次枚举了相同的数字
                continue;
            sub.push_back(nums[i]);
            backtrack(nums,len,sub,i+1);
            sub.pop_back();
        }
    }
};

 

全排列II (含重复)

class Solution {
    HashSet <List<Integer>> set = new HashSet<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        boolean used[] = new boolean[nums.length];
        permute(new ArrayList<Integer>(),nums, used);
        return new ArrayList(set);
    }
    
    public void permute(List<Integer> permutation, int []nums,  boolean used[]){
                
        if(permutation.size() == nums.length){
            set.add(new ArrayList<Integer>(permutation));
            return;
        }

        for(int i = 0; i < nums.length; i++){
            if(!used[i]){
                permutation.add(nums[i]);
                used[i] = true;
                permute(permutation, nums, used);
                permutation.remove(permutation.size()-1);
                used[i] =false;
            }
        }
        
    }
}

 

组合

class Solution {
public:
    
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> res;
        vector<int> tmp;
        backtrack(res,tmp,candidates,target,0);
        return res;
    }
    
    void backtrack(vector<vector<int>>& res, vector<int>& tmp, vector<int>& candidates, int target, int start){
        if(target<0) return;
        if(target==0) 
            res.push_back(tmp);
        // 带start相当于不会重复前数的三角形回溯
        for(int i=start;i<candidates.size();i++){
            tmp.push_back(candidates[i]);
            backtrack(res,tmp,candidates,target-candidates[i],i); // 每次继续找余数
            tmp.pop_back();
        }
    }
};

 

组合II (只能用一次)

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<vector<int>> res;
        vector<int> tmp;
        sort(candidates.begin(),candidates.end());
        backtrack(res,tmp,candidates,target,0);
        return res;
    }
    
    void backtrack(vector<vector<int>>& res, vector<int>& tmp, vector<int>& candidates, int target, int start){
        if(target<0) return;
        if(target==0) 
            res.push_back(tmp);
        for(int i=start;i<candidates.size();i++){
            if(i>start && candidates[i]==candidates[i-1]) 
                continue; // 如果有重复，用排序检查前数去重
            tmp.push_back(candidates[i]);
            backtrack(res,tmp,candidates,target-candidates[i],i+1); 
            tmp.pop_back();
        }
    }
};

 

回文分割

class Solution {
    
    public List<List<String>> res = new ArrayList<List<String>>();
    public List<List<String>> partition(String s) {
        backtrack(0,s,new ArrayList<String>());
        return res;
    }
    
    void backtrack(int start, String s, List<String> curr){
        if(start>=s.length()) //仅当所以字母都遍历过
            res.add(new ArrayList<String>(curr));
        for(int end = start; end<s.length();end++){
            if(isPalindrome(s,start,end)){ //只添加回文
                curr.add(s.substring(start,end+1));
                backtrack(end+1,s,curr);
                curr.remove(curr.size()-1);
            }
        }
    }
    
    Boolean isPalindrome(String s, int low, int high){
        while(low<high){
            if(s.charAt(low++)!=s.charAt(high--))
                return false;
        }
        return true;
    }
}