Subsets

Given a set ofdistinctintegers,nums, return all possible subsets.

Note:The solution set must not contain duplicate subsets.

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

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

//1 iterative
public List<List<Integer>> subsets(int[] nums) {

     ArrayList<List<Integer>> ans = new ArrayList<>();
     if(nums.length == 0) return ans;

     ans.add(new ArrayList<>());

     for(int num: nums){
         int size = ans.size();
         for(int i = 0; i < size; i ++){
             List<Integer> tmp = new ArrayList<>(ans.get(i));
             tmp.add(num);
             ans.add(tmp);
         }
     }

     return ans;
 }

 //2 recursive
 public List<List<Integer>> subsets(int[] nums) {

     ArrayList<List<Integer>> ans = new ArrayList<>();
     if(nums.length == 0) return ans;

     List<Integer> sub = new ArrayList<>();
     dfs(nums, 0, sub, ans);
     return ans;
 }

 public void dfs(int[] nums, int start, List<Integer> sub, ArrayList<List<Integer>> ans) {

     if(start > nums.length)
         return;

     ans.add(new ArrayList<>(sub));

     for(int i = start; i < nums.length; i ++){
         sub.add(nums[i]);
         dfs(nums, i + 1, sub, ans);
         sub.remove(sub.size() - 1);
     }
 }


 //3 bit manipulation
 public List<List<Integer>> subsets(int[] nums) {

     ArrayList<List<Integer>> ans = new ArrayList<>();
     if(nums.length == 0) return ans;

     int n = 1 << nums.length;
     for(int i = 0; i < n; i ++){
         ans.add(getSub(nums, i));
     }
     return ans;
 }

 public List<Integer> getSub(int[] nums, int k) {

     List<Integer> subs = new ArrayList<>();

     int index = 0;
     for(int i = k; i > 0; i = i>>1){

         if((i & 1) == 1)
             subs.add(nums[index]);
         index++;
     }
     return subs;
 }