leetcode 90. Subsets II and 78
2017-11-02 本文已影响0人
哲哲哥
Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).
Note: 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],
[]
]
首先写一个如果没有重复数字的组合,该怎么写?
可以这样考虑对与1,2,3。我们可以第一次去1,2,3然后回退到2这一层把3标注不取1,2。再到1这一层标注2不取1,3然后到1这一层1。有时我们标注一个数是“取还是不取”,使用下标idx不好标注时,我们可以考虑使用 boolean[] v 数组来标注
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class CopyOfSolution90 {
public static List<List<Integer>> ans = new LinkedList<List<Integer>>();
public static LinkedList<Integer> list = new LinkedList<Integer>();
public static boolean[] v = new boolean[100];
public static void robot(int idx, int[] nums) {
if (idx >= nums.length) {
List<Integer> temp = new ArrayList<Integer>();
for (int i = 0; i < nums.length; i++) {
if (v[i]) {
temp.add(nums[i]);
}
}
System.out.println(temp);
ans.add(temp);
return;
}
v[idx] = true;//取
robot(idx + 1, nums);
v[idx] = false;//不取
robot(idx + 1, nums);
}
public static void main(String[] args) {
int arr[] = {1,2,3};
robot(0, arr);
// System.out.println(ans);
}
}
在考虑如果有重复数字,如果这一层的数字和上一层的数字相同,但是上一层的数字没有取,那么这一层的数字也不能取
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class Solution90 {
public static List<List<Integer>> ans = new LinkedList<List<Integer>>();
public static LinkedList<Integer> list = new LinkedList<Integer>();
public static boolean[] v = new boolean[100];
public static void robot(int idx, int[] nums) {
if (idx >= nums.length) {
List<Integer> temp = new ArrayList<Integer>();
for (int i = 0; i < nums.length; i++) {
if (v[i]) {
temp.add(nums[i]);
}
}
System.out.println(temp);
ans.add(temp);
return;
}
if (idx > 0 && nums[idx - 1] == nums[idx] && v[idx - 1] == false) {
v[idx] = false;
robot(idx + 1, nums);//上次没有取说明下一次想取到一个不同的数
} else {
v[idx] = true;//取
robot(idx + 1, nums);
v[idx] = false;//不取
robot(idx + 1, nums);
}
}
public static void main(String[] args) {
int arr[] = {1,2,2};
robot(0, arr);
// System.out.println(ans);
}
}