求一个数组的所有子集数组
给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。
说明:解集不能包含重复的子集。
示例:
1 2 3 4 5 6 7 8 9 10 11 12
| 输入: nums = [1,2,3] 输出: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
|
思路1
从前往后遍历,新子集就是原子集加上新加的数。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| class Solution { public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> list = new ArrayList<>(); int len = nums.length; List<Integer> inList = new ArrayList<>(); list.add(inList); for(int i=0; i<len; i++){ int size = list.size(); for(int j = 0; j<size; j++){ List<Integer> newList = new ArrayList<>(list.get(j)); newList.add(nums[i]); list.add(newList); } } return list; } }
|
思路2
当成回溯问题求解。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| class Solution { public List<List<Integer>> subsets(int[] nums) { ArrayList<List<Integer>> res = new ArrayList<List<Integer>>(); backtracking(res, new ArrayList<Integer>(), nums, 0); return res; } private void backtracking(ArrayList<List<Integer>> res, ArrayList<Integer> arr, int[] nums, int location){ if(nums==null || nums.length==0){ res.add(arr); return; }else{ res.add(new ArrayList<Integer>(arr)); for(int i=location; i<nums.length; i++){ arr.add(nums[i]); backtracking(res, arr, nums, i+1); arr.remove(arr.size()-1); } } } }
|
题目链接