leetcode-subset

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/subsets/

　　输出数组的全部子集。

题目分析

　　输出一个数组的全部子集，这里采用暴力的深度优先搜索。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/*
  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],
    []
  ]
  Subscribe to see which companies asked this question
*/
public class Solution {
	private List<List<Integer>> res = new ArrayList<List<Integer>>();
	private Boolean[] v;
	private void search(int i, int[] nums) {
		int len = nums.length;
		if(i >= len) {
			List<Integer> ans = new ArrayList<Integer>();
			for(int ii = 0; ii < len; ii++) {
				if(v[ii] == true) {
					ans.add(nums[ii]);
				}
			}
			res.add(ans);
			return;
		}
		v[i] = true;
		search(i + 1, nums);
		v[i] = false;
		search(i + 1, nums);
	}
    public List<List<Integer>> subsets(int[] nums) {
    	int len = nums.length;
        v = new Boolean[len];
        res.clear();
        search(0, nums);
        return res;
    }
}