回溯&子集問題

烟沙 2021-08-15 18:16:49 阅读数:175

本文一共[544]字,预计阅读时长:1分钟~
回溯 子集

前言

“這是我參與8月更文挑戰的第15天,活動詳情查看:8月更文挑戰

  1. NC27 集合的所有子集(中等)
  2. 90. 子集 II

集合的所有子集

描述:現在有一個沒有重複元素的整數集合S,求S的所有子集
注意:
你給出的子集中的元素必須按昇序排列
給出的解集中不能出現重複的元素

輸入:

[1,2,3]
複制代碼

返回值:

[[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]
複制代碼

思路分析: 回溯主要是3點

  1. 結束條件
  2. 當前可以做的選擇
  3. 已經做出的選擇

impicture_20210815_135238.png

針對這個道題目,要求有序, 因此處理前後都需要進行排序

AC 代碼:

 ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
public ArrayList<ArrayList<Integer>> subsets(int[] S) {
Arrays.sort(S);
dfs(S, 0, new ArrayList<>());
Collections.sort(ans, new Comparator<ArrayList<Integer>>() {
@Override
public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) {
if (o1.size() != o2.size()) {
return o1.size() - o2.size();
}
int size = o1.size();
for (int i = 0; i < size; i++) {
if (o1.get(i).equals(o2.get(i))) continue;
return o1.get(i) - o2.get(i);
}
return 0;
}
});
return ans;
}
void dfs(int[] S, int index, ArrayList<Integer> temp) {
ans.add(new ArrayList<>(temp));
for (int i = index; i < S.length; i++) {
temp.add(S[i]);
dfs(S, i + 1, temp);
temp.remove(temp.size() - 1);
}
}
複制代碼

90. 子集 II

描述: 給你一個整數數組 nums ,其中可能包含重複元素,請你返回該數組所有可能的子集(幂集)。

解集 不能 包含重複的子集。返回的解集中,子集可以按 任意順序 排列。

思路分析: 與上面一道題目類似, 只不過給的原始數組中包含重複的元素

  1. 暴力解法,最後對結果去重
  2. 回溯 + 剪枝 同一層不可以使用重複的元素

impicture_20210815_135959.png

  1. 若前一個元素和當前元素相同,並且未被訪問,則說明前一個元素已經被使用過了。則直接跳過當前元素
  2. 若前一個元素和當前元素相同,但已被訪問,則說明當前元素在前一個元素的分支下,可以使用。

AC 代碼:

 List<List<Integer>> ans = new ArrayList<>();
boolean[] used;
public List<List<Integer>> subsetsWithDup(int[] nums) {
if (nums == null || nums.length == 0){
return new ArrayList<>();
}
Arrays.sort(nums);
used = new boolean[nums.length];
help(nums, 0, new ArrayList<>());
return ans;
}
private void help(int[] nums, int startIndex, List<Integer> temp){
ans.add(new ArrayList<>(temp));
for (int i = startIndex; i < nums.length; i++){
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]){
continue;
}
temp.add(nums[i]);
used[i] = true;
help(nums, i + 1, temp);
temp.remove(temp.size() - 1);
used[i] = false;
}
}
複制代碼
版权声明:本文为[烟沙]所创,转载请带上原文链接,感谢。 https://gsmany.com/2021/08/20210815181419026T.html