---
# System prepended metadata

title: '20200109'

---

# 20200109

https://ppt.cc/fO8Kex

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Input: nums = [1,2,3]
Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

```
public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    helper(result, new ArrayList<>(), nums, 0);
    return result;
}    
[]
[], [1]
[], [1], [1, 2]
[], [1], [1, 2], [1, 2, 3]
[], [1], [1, 2], [1, 2, 3], [1, 3]
[], [1], [1, 2], [1, 2, 3], [1, 3], [2]
[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3]
[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]
public void helper(List<List<Integer>> result, List<Integer> tempList, int[] nums, int start) {
    result.add(new ArrayList<>(tempList));
    for (int i = start; i < nums.length; i++) {
        tempList.add(nums[i]); 
        helper(result, tempList, nums, i + 1);
        tempList.remove(tempList.size() - 1);
    }
}

```


Given a binary tree, collect a tree's nodes as if you were doing this: Collect and remove all leaves, repeat until the tree is empty.

Example:

Input: [1,2,3,4,5]
  
          1
         / \
        2   3
       / \     
      4   5    

Output: [[4,5,3],[2],[1]]
 

Explanation:

1. Removing the leaves [4,5,3] would result in this tree:

          1
         / 
        2          
 

2. Now removing the leaf [2] would result in this tree:

          1          
 

3. Now removing the leaf [1] would result in the empty tree:

          []      

          
```
```public List<List<Integer>> findLeaves(TreeNode root) {
        
        List<List<Integer>> leavesList = new ArrayList< List<Integer>>();
        List<Integer> leaves = new ArrayList<Integer>();
        
        while(root != null) { 
            if(isLeave(root, leaves)) 
                root = null;
            leavesList.add(leaves);
            leaves = new ArrayList<Integer>();
        }
        return leavesList;
    }
    
    public boolean isLeave(TreeNode node, List<Integer> leaves) {
        
        if (node.left == null && node.right == null) {
            leaves.add(node.val);
            return true;
        }
        
        if (node.left != null) {  
             if(isLeave(node.left, leaves))  node.left = null;
        } 
        
        if (node.right != null) {
             if(isLeave(node.right, leaves)) node.right = null;
        } 
         
        return false;
    }
```
          
          
```
public List<List<Integer>> findLeaves(TreeNode root) {
    List<List<Integer>> list = new ArrayList<>();
    findLeavesHelper(list, root);
    return list;
}
        
  // return the level of root
private int findLeavesHelper(List<List<Integer>> list, TreeNode root) {
    if (root == null) {
        return -1;
    }
    // 1
    int leftLevel = findLeavesHelper(list, root.left); //  1
    int rightLevel = findLeavesHelper(list, root.right); // 0
    int level = Math.max(leftLevel, rightLevel) + 1;
    if (list.size() == level) { // 0
        list.add(new ArrayList<>()); // [4, 5], [2], [1]
    }
    list.get(level).add(root.val); // [4, 5, 3]
    root.left = null;
    root.right = null;
    return level;
}
```