LeetCode-Subsets(子集)

妖狐艹你老母 2022-08-06 18:30 170阅读 0赞

Given a set of distinct integers, S, 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 S = `[1,2,3]`, a solution is:

[
      [3],
      [1],
      [2],
      [1,2,3],
      [1,3],
      [2,3],
      [1,2],
      []
    ]

上代码：

public List<List<Integer>> subsets(int[] S) {
            Arrays.sort(S);
            List<List<Integer>> lists = new ArrayList<>();
            boolean[] visit = new boolean[S.length];
            allSubsets(S, lists, 0, visit);
            return lists;
        }
        private void allSubsets(int[] a, List<List<Integer>> lists, int depth, boolean[] visit) {
        	if (depth == a.length) {
        		List<Integer> list = new ArrayList<>();
    			for (int i = 0; i < a.length; i++) {
    				if (visit[i]) {
    					list.add(a[i]);
    				}
    			}
    			lists.add(list);
    		} else {
    			visit[depth] = true;
    			allSubsets(a, lists, depth+1, visit);
    			visit[depth] = false;
    			allSubsets(a, lists, depth+1, visit);
    		}
        }

不使用visit标记：

public List<List<Integer>> subsets(int[] S) {
            		Arrays.sort(S);
    		List<List<Integer>> lists = new ArrayList<>();
    		List<Integer> list = new ArrayList<>();
    		allSubsets(S, 0, lists, list);
    		return lists;
        }
        private void allSubsets(int[] a, int depth, List<List<Integer>> lists, List<Integer> list) {
        	if (depth == a.length) {
    			lists.add(new ArrayList<>(list));
    			return;
    		} 
        	list.add(a[depth]);
    		allSubsets(a, depth+1, lists, list);
    		list.remove(list.size()-1);
    		allSubsets(a, depth+1, lists, list);
        }

当然使用迭代的办法也可以完成：

public List<List<Integer>> subsets1(int[] S) {
    		List<List<Integer>> results = new ArrayList<List<Integer>>();
    		results.add(new ArrayList<Integer>());
    		Arrays.sort(S);
    		for (int i = 0; i < S.length; i++) {
    			int curr = S[i];
    			int curLen = results.size();
    			for (int j = 0; j < curLen; j++) {
    				List<Integer> copy = new ArrayList<>(results.get(j));
    				copy.add(curr);
    				results.add(copy);
    			}
    		}
    		return results;
    	}

三种方法，效率最高的是第二种方法！！！

如果有重复数字呢？比如

For example,  
If nums = `[1,2,2]`, a solution is:

[
      [2],
      [1],
      [1,2,2],
      [2,2],
      [1,2],
      []
    ]

一种方法就是把List<Integer>改为Set<Integer>，用Set这种集合自己去重的功效。在一个就是改造迭代方法，如下：

public List<List<Integer>> subsetsWithDup(int[] nums) {
            List<List<Integer>> lists = new ArrayList<>();
            if (nums == null || nums.length == 0) return lists;
            Arrays.sort(nums);
            
            int curLen = 0;
            lists.add(new ArrayList<Integer>());
            for (int i = 0; i < nums.length; i++) {
                int len = lists.size();
                int start = (i > 0 && nums[i-1] == nums[i]) ? curLen : 0;
                for (int j = start; j < len; j++) {
                    List<Integer> temp = new ArrayList<Integer>(lists.get(j));
                    temp.add(nums[i]);
                    lists.add(temp);
                }
                curLen = len;
            }
            
            return lists;
        }