2022-03-24 II 083. 082回溯

083:
java版本：

class Solution {
    List<List<Integer>> res=new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        List<Integer> list=new ArrayList<>();
        int n=nums.length;
      

        DFS(nums,0,n,list);
        return res;

    }
    public void DFS(int[] nums,int index,int n,List<Integer> list){
          if(list.size()==n){ 
               res.add(new ArrayList<Integer>(list));  
            return;
        }
     
       
        for(int i=0;i<n;i++){ 
            if (list.contains(nums[i])) continue;   
             list.add(nums[i]);
             DFS(nums,i,n,list);   
            list.remove(list.size()-1);       
        }
     
           
    }
}

082：
java版本：

class Solution {
     List<List<Integer>> res;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        int n=candidates.length;

       res=new ArrayList<List<Integer>>();
        List<Integer> list=new ArrayList<>();
       Arrays.sort(candidates);
         
           DFS(candidates,target,0,n,list);
           return res;
        
    }
    public void DFS(int[] candidates,int target,int index,int n,List<Integer> list){

        if(target==0){
            res.add(new ArrayList<>(list));
            return;
        }


      
        for(int i=index;i<n;i++){
            if(candidates[i]>target){
                break;
            }
            if(i>index && candidates[i]==candidates[i-1]){
                continue;
            }
      list.add(candidates[i]);
    DFS(candidates,target-candidates[i],i+1,n,list);
    list.remove(list.size()-1);

        }
        
    }
}