歡迎關(guān)注個(gè)人公眾號：愛喝可可牛奶
LeetCode算法訓(xùn)練-回溯 491.遞增子序列 46.全排列 47.全排列 II
LeetCode 491. 遞增子序列
分析
找出并返回所有數(shù)組中不同的遞增子序列
絕對不能先升序 絕對不能先升序 絕對不能先升序 這樣會改變原有數(shù)組的結(jié)構(gòu)
子序列中元素在數(shù)組中不一定相鄰
只要葉子節(jié)點(diǎn)檬嘀，也就是path每篷，一滿足條件吨拗，直接加入res
注意去重used[] 數(shù)組只針對當(dāng)前節(jié)點(diǎn)的后序節(jié)點(diǎn) 要在回溯函數(shù)中定義 畫回溯樹一看便知
代碼
class Solution {
private LinkedList<Integer> path = new LinkedList<>();
private List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> findSubsequences(int[] nums) {
backtracking(nums,0);
return res;
}
private void backtracking (int[] nums, int start) {
// 保證了能進(jìn)入path的元素是升序的
if (path.size() > 1) {
res.add(new LinkedList<>(path));
// 注意這里不要加return检柬，要取樹上的節(jié)點(diǎn)
}
// 元素值為used數(shù)組索引 只對同一行進(jìn)行去重
int[] used = new int[201];
for (int i = start; i < nums.length; i++) {
// path 為空 當(dāng)前元素小于path最后一個(gè)元素 或者這個(gè)元素在本層已經(jīng)使用過了 跳過這個(gè)繼續(xù)橫向遍歷
if (!path.isEmpty() && nums[i] < path.getLast() || (used[nums[i] + 100] == 1)) {
// 如果是break 應(yīng)該是終止當(dāng)前節(jié)點(diǎn)的橫向遍歷 進(jìn)入遞歸
continue;
}
used[nums[i] + 100] = 1;
path.add(nums[i]);
backtracking(nums, i + 1);
path.removeLast();
}
}
}
LeetCode 46. 全排列
分析
全排列，收集回溯樹的葉子節(jié)點(diǎn)即可 注意終止條件要return
But 因?yàn)樗阉鬟^程每次都從第一個(gè)元素開始茴恰，要記錄哪些元素已經(jīng)使用過了 used[]數(shù)組應(yīng)該是全局的
代碼
class Solution {
List<List<Integer>> result = new ArrayList<>();// 存放符合條件結(jié)果的集合
LinkedList<Integer> path = new LinkedList<>();// 用來存放符合條件結(jié)果
boolean[] used;
public List<List<Integer>> permute(int[] nums) {
if (nums.length == 0){
return result;
}
used = new boolean[nums.length];
permuteHelper(nums);
return result;
}
private void permuteHelper(int[] nums){
if (path.size() == nums.length){
result.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++){
if (used[i]){
continue;
}
used[i] = true;
path.add(nums[i]);
permuteHelper(nums);
path.removeLast();
used[i] = false;
}
}
}
LeetCode 47. 全排列 II
分析
按任意順序 返回所有不重復(fù)的全排列
涉及到如何去重 根據(jù)用例畫一個(gè)回溯樹看看
在橫向遍歷時(shí)颠焦，如果當(dāng)前元素==前一個(gè)元素，continue往枣；
難點(diǎn)：如何判斷統(tǒng)一樹層當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)使用過 去看一下當(dāng)前節(jié)點(diǎn)前一個(gè)節(jié)點(diǎn)的狀態(tài)
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
continue;
}
代碼
class Solution {
List<List<Integer>> result = new ArrayList<>();// 存放符合條件結(jié)果的集合
LinkedList<Integer> path = new LinkedList<>();// 用來存放符合條件結(jié)果
public List<List<Integer>> permuteUnique(int[] nums) {
if (nums.length == 0){
return result;
}
// 得先排個(gè)序才能保證前后元素比較的正確性
Arrays.sort(nums);
boolean[] used = new boolean[nums.length];
permuteHelper(nums,used);
return result;
}
private void permuteHelper(int[] nums, boolean[] used){
if (path.size() == nums.length){
result.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++){
// 一定要通過used保證nums[i-1]是樹層上nums[i]的前一個(gè)元素
if(i > 0 && nums[i] == nums[i-1] && !used[i-1]){
continue;
}
if (!used[i]){
used[i] = true;
path.add(nums[i]);
permuteHelper(nums,used);
path.removeLast();
used[i] = false;
}
}
}
}
總結(jié)
- 組合問題和排列問題是在樹形結(jié)構(gòu)的葉子節(jié)點(diǎn)上收集結(jié)果伐庭，而子集問題就是取樹上所有節(jié)點(diǎn)的結(jié)果
- 理清回溯樹樹層、樹枝的節(jié)點(diǎn)關(guān)系 for循環(huán)處理的是樹層分冈，遞歸調(diào)用函數(shù)處理的是樹枝
- 如果沒有startIndex來確定取的是數(shù)組中哪一個(gè)元素圾另，used[]數(shù)組+for循環(huán)能間接確定這個(gè)元素是不是取過
