给定一个int数组，找出所有的子集；结果要排好序
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], [] ]
Java代码:
1 package com.rust.datastruct; 2 3 import java.util.ArrayList; 4 import java.util.Collections; 5 import java.util.List; 6 7 class SubsetsSolution { 8 public List<List<Integer>> subsets(int[] nums) { 9 List<List<Integer>> res = new ArrayList<List<Integer>>(); 10 List<Integer> temp = new ArrayList<Integer>(); 11 res.add(temp);/* the empty subset: [] */ 12 findSubsets(nums, 0, temp, res); 13 return res; 14 } 15 private void findSubsets(int nums[],int start, List<Integer> singleSet, 16 List<List<Integer>> result){ 17 if (start >= nums.length){ 18 return; 19 } 20 for (int i = start; i < nums.length; i++) { 21 /*keep singleSet*/ 22 List<Integer> subset = new ArrayList<Integer>(singleSet); 23 subset.add(nums[i]); 24 Collections.sort(subset); 25 result.add(subset);/*put in result*/ 26 findSubsets(nums, i + 1, subset, result); 27 } 28 } 29 } 30 public class Subsets { 31 private static SubsetsSolution solution; 32 private static List<List<Integer>> res; 33 public static void main(String args[]){ 34 int nums[] = {1,4,3,2}; 35 solution = new SubsetsSolution(); 36 res = solution.subsets(nums); 37 for (int i = 0; i < res.size(); i++) { 38 System.out.println(res.get(i)); 39 } 40 } 41 }
输出：
[] [1] [1, 4] [1, 3, 4] [1, 2, 3, 4] [1, 2, 4] [1, 3] [1, 2, 3] [1, 2] [4] [3, 4] [2, 3, 4] [2, 4] [3] [2, 3] [2]
递归处理问题。从输出结果可以看出处理的流程。
找到第一个数，这里是“1”，然后“1”保持不动，找下一个数“4”。然后“1”和“4”不动，再接着找。
每个元素都有机会作为开头的数。从左往右遍历一次，每次都会找当前数的右边的可能组合。
