回溯法——总结（是否包含重复元素，是否全排列）

class Solution {
    List> res;
    List path;
    public List> permute(int[] nums){
        res = new ArrayList<>();
        path = new ArrayList<>();
        int[] visited = new int[nums.length];
        dfs(nums, visited);
        return res;
    }
    public void dfs(int[] nums, int[] visited) {
        if(path.size() == nums.length){
            res.add(new ArrayList(path));
            return;
        }
        for(int i=0; i 
 
class Solution {
    public String[] permutation(String s) {
        List res = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        char[] arr = s.toCharArray();
        Arrays.sort(arr);
        boolean[] used = new boolean[s.length()];
        backtracking(0, sb, res, used, arr);
        return res.toArray(new String[res.size()]);   //?
    }
    private void backtracking(int level, StringBuilder sb, List res, boolean[] used, char[] arr){
        if(level == arr.length){
            res.add(sb.toString());
            return;
        }
        for(int i=0; i0 && arr[i]==arr[i-1] && !used[i-1])  continue;
            sb.append(arr[i]);
            used[i] = true;
            backtracking(level+1, sb, res, used, arr);
            sb.deleteCharAt(sb.length()-1);
            used[i] = false;
        }
    }
}
 
 
class Solution {
    List> res;
    linkedList path;
    public List> permuteUnique(int[] nums) {
        res = new linkedList<>();
        path = new linkedList<>();
        boolean[] visited = new boolean[nums.length];
        Arrays.sort(nums);
        dfs(nums, visited);
        return res;
    }
    public void dfs(int[] nums, boolean[] visited){
        if(path.size() == nums.length){
            res.add(new linkedList(path));
            return;            
        }   
        for(int i=0; i0 && nums[i] == nums[i-1] && !visited[i-1])    continue;  
            if(visited[i])    continue;
            path.add(nums[i]);
            visited[i] = true;
            dfs(nums,visited);
            visited[i] = false;
            path.removeLast();
        }
    }
}
 
 
class Solution {
    linkedList> res;
    linkedList path;
    public List> combinationSum(int[] candidates, int target) {
        res = new linkedList<>();
        path = new linkedList<>();
        Arrays.sort(candidates);
        dfs(candidates, 0, target);
        return res;
        
    }
    public void dfs(int[] candidates, int index, int target) {
        if(target == 0) {
            res.add(new linkedList<>(path));
            return;
        }
        for(int i=index; i 
 
class Solution {
    linkedList path;
    linkedList> res;
    public List> combinationSum2(int[] candidates, int target) {
        path = new linkedList<>();
        res = new linkedList<>();
        Arrays.sort(candidates);
        dfs(candidates, 0,target);
        return res;
    }
    public void dfs(int[] candidates, int index, int target) {
        if(target == 0){
            res.add(new linkedList(path));
            return;
        }
        for(int i=index; iindex && candidates[i] == candidates[i-1])   continue;
            path.add(candidates[i]);
            dfs(candidates,i+1,target-candidates[i]);
            path.removeLast();   
        }
    }
}