LC.78. + LF.62. SubsetsI

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

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>() ; 
        if(nums == null ){
            return res ; 
        }
        List<Integer> sol = new ArrayList<>(); 
        helper(nums, res, 0, sol) ; 
        return res ; 
    }
    private void helper(int[] nums, List<List<Integer>> res , int index, List<Integer> sol){
        //termination point: note sol here is reference type so make a deep copy
        if(index == nums.length ){
            res.add(new ArrayList<>(sol)); 
            return ; 
        }
        //case 1: add
        sol.add(nums[index]) ;
        helper(nums, res, index+1 , sol) ;
        sol.remove(sol.size()-1);
        //case 2: dont add
        helper(nums, res, index+1 , sol) ;
    }
}

time:  o(2^n) elements 

space: o(n)  # of calling stacks

LF.62:

Given a set of characters represented by a String, return a list containing all subsets of the characters.

Assumptions

There are no duplicate characters in the original set.
​Examples

Set = "abc", all the subsets are [“”, “a”, “ab”, “abc”, “ac”, “b”, “bc”, “c”]
Set = "", all the subsets are [""]
Set = null, all the subsets are []

public class Solution {
  public List<String> subSets(String set) {
    // Write your solution here.
    List<String> res = new ArrayList<>() ;
    if (set == null) {
        return res ;
    }
    char[] arraySet = set.toCharArray() ;
    StringBuilder sol = new StringBuilder() ;
    helper(arraySet,res, 0 , sol);
    return res ;
  }
  /*
    index: 控制第几层
  */
  private void helper(char[] set, List<String> res, int index, StringBuilder sol ){
    /*terminate condition:
    when we finishes determining for all the chars pick or not,
    we have a complete subset.
    */
    if (index == set.length) {
        res.add(sol.toString()) ;
        return ;
    }
    //case 1: pick the character at index
    helper(set,res,index+1,sol.append(set[index]));
    //remember to remove the added character when back tracking to //the previous level
    sol.deleteCharAt(sol.length()-1) ;
    //case 2: not pick the character at index
    helper(set,res,index+1, sol);
  }
}