Leetcode 78: subset

link
subject ：

Ideas ： to flash back （ No duplicate elements cannot be checked ）

Backtracking framework ：

This question is form one ： No duplicate elements cannot be checked , When writing backtracking algorithms ,for It's from start Start , Not from 0 Start ！ namely （2,1） and （1,2） It's a result , Therefore, you cannot check .
use start To ensure that each recursion traverses the number not traversed after the array , Instead of iterating over the previous number
Last strat If the number of arrays exceeds Termination conditions ！

Be careful ：
Subset problem , Each node is a subset ！
Need to be recursive 【 Preamble position 】 take path Add to res ！ Instead of adding to the leaf node res !
An empty set [ ] Also operator set

Java Realization ：

class Solution {
    
    List<List<Integer>> res=new LinkedList<>();
    LinkedList<Integer> path=new LinkedList<>();

    public List<List<Integer>> subsets(int[] nums) {
    
        if(nums==null){
    
            return new List<List<Integer>>;
        }
        dfs(nums,0);
        return res;
    }

    void dfs(int[] nums,int start){
    
  // use start To ensure that each recursion traverses the number behind the array , Instead of iterating over the previous number ,
  // Last strat Exceeding the number of arrays is the termination condition ！
  //  An empty set [] Also operator set 
        res.add(new LinkedList(path)); //  Each node is a subset  ！ Instead of adding to the leaf node res !

        for(int i=start;i<nums.length;i++){
    
            // Select before recursion 
            path.add(nums[i]);
            // recursive ,i+1 Ensure that the elements in the array are not reused 
            dfs(nums,i+1);
            // Undo after recursion 
            path.removeLast();
        }
    }
}