Subsets
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], []]
回溯法
说明
一道经典的回溯问题, 要注意的是在leetcode中如果想AC的话数组必须先排序才可以.
复杂度
因为长度为n的数组的子集个数为2^n
时间O(2^n) 空间O(2^n)代码
public List
> subsets(int[] nums) { List
> res = new ArrayList
>(); if (nums == null || nums.length == 0) { return res; } List tem = new ArrayList (); Arrays.sort(nums); helper(res, tem, nums,0); return res;}public void helper(List
> res, List tem, int[] nums, int index) { res.add(new ArrayList (tem));//防止引用修改所以要new 一个list if (index >= nums.length) { return; } for (int i = index; i < nums.length; i++) { tem.add(nums[i]); helper(res, tem, nums, i + 1); tem.remove(tem.size() - 1); }}
Subsets II
Given a collection of integers that might contain duplicates, 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,2], a solution is:[ [2], [1], [1,2,2], [2,2], [1,2], []]
回溯法
说明
与i不同的是有重复的数字， 例如[1,2(1)] [1,2(2)]情况相同， 递归过程中每次新选取的可以是和递归数组相同的，（比如nums是[1，2，2，2］ 当前递归栈是［1，2（1）］ 新加入的［1，2(1), 2(2)]是合法的） 但是后面的元素就不能相同了（［1, 2(1), 2(3)]就不合法 因为重复了）。
新选取的元素在递归栈里就是每次当i取index得值时候, 所以当i!=index的值时候来去重复杂度
时间O(2^n) 空间O(2^n)
代码
public List
> subsetsWithDup(int[] nums) { List
> res = new ArrayList
>(); if (nums == null || nums.length == 0) { return res; } List tem = new ArrayList (); Arrays.sort(nums); helper(res, tem, nums,0); return res;}public void helper(List
> res, List tem, int[] nums, int index) { res.add(new ArrayList (tem)); if (index >= nums.length) { return; } for (int i = index; i < nums.length; i++) { //去重复: if (i != index && nums[i] == nums[i - 1]) { continue; } tem.add(nums[i]); helper(res, tem, nums, i + 1); tem.remove(tem.size() - 1); } }