L78. Subsets

dfs

Problem:

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

Note: The solution set must not contain duplicate subsets.

Example:

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

Solution:

• use backtracking function to create all possible sets

public List<List<Integer> subSet(int[] nums){
    List<List<Integer>> ans = new ArrayList<>():
    if(nums == null) return ans;
    Array.sort(nums);
    dfs(ans, nums, new ArrayList<Integer>(), 0);
    return ans;
}
public void dfs(List<List<Integer> ans, int[] nums, List<Integer> list, int index){
    if(index == nums.lenght){
        ans.add(new ArrayList<Integer>(), 0);
        return;        
    }
    dfs(ans, nums, list, index+1);
    list.add(nums[index]);
    dfs(ans,nums, list, index+1);
    list.remove(list.size()-1);
}