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

算法

深度优先，回溯算法

代码

        public List<List<Integer>> subsets(int[] nums) {
	        List<List<Integer>> res = new ArrayList<>();
	        dfs(res, new ArrayList<>(), nums, 0);
	        return res;
	    }
	    
	    public void dfs(List<List<Integer>> res, List<Integer> list, int[] nums, int start) {
	    	res.add(new ArrayList<>(list));
	    	for(int i=start;i<nums.length;i++) {
	    		list.add(nums[i]);
	    		dfs(res, list, nums, i+1);
	    		list.remove(list.size()-1);
	    	}
	    }