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

Analysis:

DFS, to create combination without using duplicate elements, next level of recursion should start at i+1, and we can add condition to check if remaining element is sufficient to fill rest of combination.

Complexity:

Time: O()

Space: O(N)

Code:

public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> returnList = new ArrayList<List<Integer>>();
        returnList.add(new ArrayList<Integer>());
        if(nums == null || nums.length == 0){
            return returnList;
        }

        List<Integer> tempList = new ArrayList<Integer>();
        for(int i = 1; i <= nums.length; i++){
            dfs(returnList, tempList, i, nums, 0);
        }

        return returnList;
    }

    private void dfs(List<List<Integer>> returnList, List<Integer> tempList, int len, int[] nums, int pos){
        if(tempList.size() == len){
            returnList.add(new ArrayList<Integer>(tempList));
            return;
        }

        if(len - tempList.size() > nums.length - pos) return;

        for(int i = pos; i < nums.length; i++){
            tempList.add(nums[i]);
            dfs(returnList, tempList, len, nums, i+1);
            tempList.remove(tempList.size() - 1);
        }
    }
}