backtrack 经典题
与permutation不同的是每一个中间结果都要加入到最终结果
注意递归时传入的位置是 i + 1 而不是pos+1
时间复杂度O(2^n) 因为一个长度为n的集合有2^n个子集 每个元素可选可不选，两种可能
原先在findSubsets中加入了if(pos == nums.length) return 其实是没有必要的，在这种情况下会直接跳过for循环，这样代码更简洁
1 public class Solution { 2 public List<List<Integer>> subsets(int[] nums) { 3 List<List<Integer>> result = new ArrayList<List<Integer>>(); 4 if (nums == null || nums.length == 0) { 5 return result; 6 } 7 Arrays.sort(nums); 8 List<Integer> path = new ArrayList(); 9 findSubsets(nums, 0, result, path); 10 return result; 11 } 12 13 private void findSubsets(int[] nums, int pos, List<List<Integer>> result, List<Integer> path) { 14 result.add(new ArrayList(path)); 15 for (int i = pos; i < nums.length; i++) { 16 path.add(nums[i]); 17 findSubsets(nums, i + 1, result, path); 18 path.remove(path.size() -1); 19 } 20 } 21 }
原文：http://www.cnblogs.com/ilovenaomi/p/4886864.html