Subsets

Given a set of distinct integers, nums, return all possible subsets.

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],
  []
]

Solution 1: recursive solution, beats 13% of java submissions

public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        /* i<=nums.length */
        for(int i=0; i<=nums.length; i++){
            ans.addAll(subsets(nums,i,nums.length));
        }
        return ans;
    }
    public List<List<Integer>> subsets(int[] nums, int k, int n){
        List<List<Integer>> ans = new ArrayList<>();
        /* k==0 return a List<List<Integer>> with an empty List<Integer> */
        if(k==0){
            List<Integer> tmp = new ArrayList<>();
            ans.add(tmp);
            return ans;
        }
        /* k>0 return an empty List<List<Integer>> */
        if(k>n) return ans; 
        List<List<Integer>> part1 = subsets(nums, k, n-1);
        List<List<Integer>> part2 = subsets(nums, k-1, n-1);
        for(List<Integer> list : part2){
            list.add(nums[n-1]);
        }
        part1.addAll(part2);
        return part1;
    }
}

Solution 2: iterative solution, beats 36% of java submissions

public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        ans.add(new ArrayList<Integer>());
        for(int i=0; i<nums.length; i++){
            List<List<Integer>> newAns = new ArrayList<>();
            for(int j=0; j<ans.size(); j++){
                List<Integer> newList = new ArrayList<>(ans.get(j));
                newList.add(nums[i]);
                newAns.add(newList);
            }
            newAns.addAll(ans);
            ans = newAns;
        }
        return ans;
    }
}