There are to algorithm problem about backtracking.
78. Subsets
Description
Given a set of distinct integers, nums, return all possible subsets.
Note: The solution set must not contain duplicate subsets.
For example,
If nums = [1,2,3], a solution is:
|
1 2 3 4 5 6 7 8 9 10 11 |
[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ] |
Answer
My answer is using recursion with a helper function, which is easy to understand.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> result = new ArrayList<>(); helper(result, new ArrayList<>(), nums, 0); return result; } public void helper(List<List<Integer>> result,List<Integer> single, int[] nums, int start){ result.add(new ArrayList<>(single)); for(int i=start;i<nums.length;i++){ single.add(nums[i]); System.out.println("add"+nums[i]); helper(result, single, nums, i+1); System.out.println("remove+"+single.get(single.size()-1)); single.remove(single.size()-1); } } |
90. Subsets II
Description
Given a collection of integers that might contain duplicates, nums, return all possible subsets.
Note: The solution set must not contain duplicate subsets.
For example,
If nums = [1,2,2], a solution is:
|
1 2 3 4 5 6 7 8 9 |
[ [2], [1], [1,2,2], [2,2], [1,2], [] ] |
Answer
What the difference from the first one, is that the array contains duplicates, which we should ignore in our answer.
As a result, using a sort function is necessary and we have to judge in the helper if the number is duplicate.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
public List<List<Integer>> subsetsWithDup(int[] nums) { List<List<Integer>> result = new ArrayList<>(); if(nums == null || nums.length == 0) return result; Arrays.sort(nums); helper(result, new ArrayList<Integer>(), 0, nums); return result; } public void helper(List<List<Integer>> result, List<Integer> single, int start, int[] nums){ result.add(new ArrayList<>(single)); for(int i=start;i<nums.length;i++){ if(i>start&&nums[i]==nums[i-1]) continue; single.add(nums[i]); helper(result, single, i+1, nums); single.remove(single.size()-1); } } |