回溯：剪枝总结 排列组合

import java.util.ArrayList;
import java.util.Stack;
class Solution {
    List<List<Integer>> res =new ArrayList<List<Integer>>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        if(candidates==null || candidates.length==0){
            return res;
        }
        Stack<Integer> s=new Stack<>();
        core(candidates,target,0,s);
        return res;
    }
    public void core(int[] candidates,int target,int begin,Stack s){
        if(target<0){
            return;
        }
        if(target==0){
            res.add(new ArrayList(s));
            return;
        }
        for(int i=begin;i<candidates.length;i++){
            s.push(candidates[i]);
            core(candidates,target-candidates[i],i,s);
            s.pop();
        }
    }
}

import java.util.Stack;
import java.util.ArrayList;
import java.util.Arrays;
class Solution {
    List<List<Integer>> res=new ArrayList<List<Integer>>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        if(candidates==null || candidates.length==0){
            return res;
        }
        Stack<Integer> s=new Stack<Integer>();
        Arrays.sort(candidates);
        core(candidates,target,s,0);
        return res;
    }
    public void core(int[] candidates, int target,Stack s,int begin){
        if(target<0) return;
        if(target==0){
            res.add(new ArrayList<Integer>(s));
            return;
        }
        for(int i=begin;i<candidates.length;i++){//总体来看，这一支的i==begin
                                                //i>begin时才是下一支
            if(i > begin && i-1>=0 && candidates[i-1]==candidates[i]){
                continue;
            }
            s.push(candidates[i]);
            core(candidates,target-candidates[i],s,i+1);
            s.pop();
        }
    }
}

import java.util.Stack;
import java.util.ArrayList;
class Solution {
    List<List<Integer>> res=new ArrayList<List<Integer>>();
    public List<List<Integer>> permute(int[] nums) {
        if(nums==null || nums.length==0){
            return res;
        }
        Stack<Integer> s=new Stack<Integer>();
        boolean[] used = new boolean[nums.length];//表示这个数在这一支中是否被使用
        core(nums,0,s,used);
        return res;
    }
    public void core(int[] nums,int depth,Stack s,boolean[] used){
        if(depth==nums.length){//控制深度
            res.add(new ArrayList<Integer>(s));
            return;
        }
        for(int i=0;i<nums.length;i++){//控制支数
            if(!used[i]){//如果在这一支中没有使用
                s.push(nums[i]);
                used[i]=true;
                core(nums,depth+1,s,used);
                used[i]=false;
                s.pop();
            }
        }
    }
}

import java.util.Stack;
import java.util.ArrayList;
import java.util.Arrays;
class Solution {
    List<List<Integer>> res=new ArrayList<List<Integer>>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        if(nums==null || nums.length==0){
            return res;
        }
        Arrays.sort(nums);
        Stack<Integer> s=new Stack<Integer>();
        boolean[] used = new boolean[nums.length];//表示这个数在这一支中是否被使用
        core(nums,0,s,used);
        return res;
    }
    public void core(int[] nums,int depth,Stack s,boolean[] used){
        if(depth==nums.length){//控制深度
            res.add(new ArrayList<Integer>(s));
            return;
        }
        for(int i=0;i<nums.length;i++){//控制支数
         if (used[i]) {
                continue;
            }
            // 剪枝条件：i > 0 是为了保证 nums[i - 1] 有意义
            // 写 !used[i - 1] 是因为 nums[i - 1] 在深度优先遍历的过程中刚刚被撤销选择
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
                continue;
            }
            s.push(nums[i]);
            used[i]=true;
            core(nums,depth+1,s,used);
            used[i]=false;
            s.pop();
        }
    }
}