一、题目
1、审题
2、分析
给出一个整数数组，求其所有的不重复的子数组集合。
二、解答
1、思路：
方法一、采用回溯法。
①、通过确定子集合数组的元素个数进行元素的字典排列。返回的是字典序的有序序列
public List
> subsets(int[] nums) { List
> resultList = new ArrayList
>(); int len = nums.length; if(len == 0) return resultList; int targetLen = 0; while(targetLen <= len) { helper2(resultList, new ArrayList (), nums, 0, targetLen, len); targetLen++; } return resultList; } private void helper2(List
> resultList, ArrayList arrayList, int[] nums, int startIndex, int targetLen, int len) { if(0 == targetLen) { resultList.add(new ArrayList<>(arrayList)); return; } for(int i = startIndex; i < len; i++) { arrayList.add(nums[i]); helper2(resultList, arrayList, nums, i+1, targetLen-1, len); arrayList.remove(arrayList.size()-1); } }
②、直接将子集合全部返回并进行回溯。
public List
> subsets2(int[] nums) { List
> list = new ArrayList<>(); Arrays.sort(nums); backtrack(list, new ArrayList (), nums, 0); return list; } private void backtrack(List
> list , ArrayList tempList, int [] nums, int start){ list.add(new ArrayList<>(tempList)); // 所有子集合全部放入 for(int i = start; i < nums.length; i++){ tempList.add(nums[i]); backtrack(list, tempList, nums, i + 1); tempList.remove(tempList.size() - 1); } }
方法二、直接创建一个 List 存放所有子集，遍历数组；
每次向 List 中添加新的子集：即所有已经存在子集中添加此次遍历的元素。
①、创建新的临时 List： List<List<Integer>> tmpResultList
public List
> subsets4(int[] nums) { List
> resultList= new ArrayList<>(); resultList.add(new ArrayList ()); for(int num: nums) { // 新建一个 tmpResultList，防止在遍历 resultList 时对其修改抛出 ConcurrentModificationException 异常 List
> tmpResultList= new ArrayList<>(); for(List list: resultList) { List tmpList = new ArrayList<>(list); tmpList.add(num); tmpResultList.add(new ArrayList<>(tmpList)); } resultList.addAll(tmpResultList); } return resultList; }
②改进
public List
> subsets(int[] nums) { List
> resultList= new ArrayList<>(); resultList.add(new ArrayList ()); for(int num: nums) { int size = resultList.size(); for (int i = 0; i < size; i++) { List subList = new ArrayList<>(resultList.get(i)); subList.add(num); resultList.add(subList); } } return resultList; }