Subsets | Leetcode

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

Note:

• Elements in a subset must be in non-descending order.
• 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: Sort the input array first. Initialize answer list. Then recurse starting from starting index 0. In each recursion, add given list as answer. Then loop through the input array starting from given index till the end. Collect each unique answer as you encounter them.

public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> answer = new ArrayList<>();
        subsets(answer, new ArrayList<Integer>(nums.length), 0, nums);
        return answer;
    }
    
    private void subsets(List<List<Integer>> answer, List<Integer> list, int start, int[] nums) {
        answer.add(new ArrayList<Integer>(list));
        if (start >= nums.length) return;
        
        for (int i = start; i < nums.length; i++) {
            list.add(nums[i]);
            subsets(answer, list, i + 1, nums);
            list.remove(list.size() - 1);
        }
    }
}