[LeetCode-78] SubSets
Given a set of distinct integers, nums, return the possible subsets.
回溯 + 遞歸
時(shí)間復(fù)雜度 O(n^2)
空間復(fù)雜度 O(n)
代碼
public class Solution {
public List<List<Integer>> subSets(int[] nums) {
List<Integer> list = new ArrayList<>();
List<List<Integer>> res = new ArrayList<>();
helper(nums, res, list, 0);
return res;
}
private void helper(int[] nums, List<List<Integer>> res, List<Integer> list, int pos) {
res.add(new ArrayList<>(list));
for (int i = pos; i < nums.length; i++) {
list.add(nums[i]);
helper(nums, res, list, i + 1);
list.remove(list.size() - 1);
}
}
}
[LeetCode-90] SbuSets II
Given a collection of integer that may contain duplicates, nums, return the possible subsets.
回溯 + 遞歸，首先排序。遞歸的時(shí)候跳過重復(fù)元素或者使用Set脸爱。
時(shí)間復(fù)雜度 O(n^2)
空間復(fù)雜度 O(n)
思路
注意
- 包含重復(fù)元素辩昆，注意去重漠酿。
- 首先排序纠亚。然后跳過重復(fù)元素劫哼。
- 如果沒有使用排序去掉重復(fù)元素洋只，則可以使用Set<List<Integer>>划乖，但是也要首先排序贬养。
- 注意回溯：list.remove(list.size() - 1);
- 遞歸方法helper()需要一個(gè)int入?yún)?pos，因?yàn)槊看芜f歸都是從當(dāng)前數(shù)組元素的下一個(gè)元素位置開始琴庵。
- 遞歸的pos位置為 i + 1误算。
- 每次添加結(jié)果集，都是另一份拷貝迷殿。如：res.add(new ArrayList<Integer>(list))儿礼。
代碼
/**
* 使用Set去掉重復(fù)結(jié)果。首先也得排序庆寺。
* 排序原因：Set中元素是List蚊夫，如果不排序，
* 即使list中元素都相同懦尝，順序不同也是不同的list知纷。
*/
public class Solution {
public List<List<Integer>> subSetsWithDup(int[] nums) {
List<Integer> list = new ArrayList<>();
Set<List<Integer>> resSet = new HashSet<>();
Arrays.sort(nums); // 首先排序
helper(nums, resSet, list, 0);
return new ArrayList<List<Integer>>(resSet);
}
private void helper(int[] nums, Set<List<Integer>> resSet, List<Integer> list, int pos) {
resSet.add(new ArrayList<>(list));
for (int i = 0; i < nums.length; i++) {
list.add(nums[i]);
helper(nums, resSet, list, i + 1);
list.remove(list.size() - 1);
}
}
}
/**
* 不使用Set，對(duì)于重復(fù)元素陵霉，需要排序后跳過重復(fù)元素琅轧。
*/
public class Solution {
public List<List<Integer>> subSetsWithDup(int[] nums) {
List<Integer> list = new ArrayList<>();
List<List<Integer>> res = new ArrayList<>();
helper(nums, res, list, 0);
return res;
}
private void helper(int[] nums, List<List<Integer>> res, List<Integer> list, int pos) {
res.add(new ArrayList<>(list));
int i = pos;
while (i < nums.length) {
list.add(nums[i]);
helper(nums, res, list, i + 1);
list.remove(list.size() - 1);
i++;
// 跳過重復(fù)元素, 出現(xiàn) i-1，避免數(shù)組越界撩匕。
while (i < nums.length && nums[i] == nums[i - 1]) {
i++;
}
}
}
}
[完]
