Given a set ofdistinctintegers,nums, return all possible subsets (the power set).

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

tag: backtracking

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();

        dfs(nums, 0, new ArrayList<>(), ans);

        return ans;
    }

    private void dfs(int[] nums, int index, List<Integer> path, List<List<Integer>> ans){

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

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