一菊碟、全排列 II
- 遞歸過程就像二叉樹纪吮，每一層遞歸結(jié)束后（回溯），看情況清理枝葉
- 遞歸函數(shù)結(jié)束條件：當(dāng)傳入的排列結(jié)果長(zhǎng)度等于數(shù)組長(zhǎng)度
- 遞歸函數(shù)執(zhí)行：
- 循環(huán)數(shù)組查找块仆，當(dāng)該元素未被訪問
- 將其標(biāo)記被訪問脐彩，是排列的一部分
- 然后加入排列結(jié)果中（至于new的原因：傳入的排列可能會(huì)有很多新的相關(guān)排列，也即是非葉結(jié)點(diǎn)）
- 接著調(diào)用遞歸函數(shù)犁河，再次組成排列結(jié)果
- 函數(shù)返回后（回溯）：判斷目前這個(gè)元素在數(shù)組中是否重復(fù)
- 重復(fù)是不需要再用來構(gòu)造排序的
- 因?yàn)閿?shù)組是被排序過了鳖枕，所以循環(huán)遍歷，直到越界或者不等于
- 該元素要被重新標(biāo)記為未加入排列桨螺，因?yàn)榭梢栽谙乱粋€(gè)元素的下一層遞歸中宾符，構(gòu)建出新的排列
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
Arrays.sort(nums);//數(shù)組排序
List<List<Integer>> ans = new ArrayList<>();
checkBack(nums, new int[nums.length], ans, new ArrayList<Integer>());
return ans;
}
private void checkBack(int[] nums, int[] memory, List<List<Integer>> ans, List<Integer> permute) {
if(permute.size() == nums.length) {
ans.add(permute);
} else {
for(int i = 0; i < nums.length; i++) {//遍歷數(shù)組
if(memory[i] == 0) {//到當(dāng)前遞歸，數(shù)組中的值不在當(dāng)前傳入permute中
memory[i] = 1;//現(xiàn)在在了
List<Integer> tpermute = new ArrayList<>(permute);
tpermute.add(nums[i]);
checkBack(nums, memory, ans, tpermute);//進(jìn)行下一層遞歸
memory[i] = 0;//遞歸結(jié)束就還未出現(xiàn)在往后構(gòu)造的排列中
while(i < nums.length - 1 && nums[i] == nums[i + 1]) {//處理重復(fù)的排列元素灭翔，不需要重復(fù)的排列
i++;//即使最后一個(gè)還是重復(fù)的魏烫，當(dāng)時(shí)在外循環(huán)中，i自增后判斷結(jié)果越界肝箱，結(jié)束循環(huán)哄褒。遞歸結(jié)束
}
}
}
}
}
}
二、組合總和
-
題目條件
- 無重復(fù)元素
- candidates數(shù)組中的元素可無限制重復(fù)選取
- 數(shù)字值煌张、數(shù)量不相等的組合就是唯一的
- 給定數(shù)組不一定按升序排列
-
思路：
- 類似二叉樹
- 遞歸回溯處理
- 每次循環(huán)從下標(biāo)index開始呐赡，保證前面的元素不再選取，因?yàn)槟男┙M合早已出現(xiàn)過
- index就是限制組合的重復(fù)構(gòu)成
- 題目要求組合的元素在數(shù)組無限選取
- 循環(huán)數(shù)組開始就要有個(gè)index開始骏融，防止重復(fù)
- 遞歸調(diào)用函數(shù)時(shí)链嘀，將組合sum值傳入萌狂，提高效率
- 當(dāng)sum和target相同，即可得到一個(gè)組合結(jié)果
- 遞歸的結(jié)束
- 循環(huán)的另一個(gè)條件sum + 當(dāng)前 下標(biāo)元素不大于target
- 否則結(jié)束循環(huán)怀泊，遞歸結(jié)束
- 數(shù)組需先排序茫藏，從而減少?zèng)]必要的遞歸（值比target大）
class Solution { public List<List<Integer>> combinationSum(int[] candidates, int target) { Arrays.sort(candidates);//先排序 List<List<Integer>> ans = new ArrayList<>(); checkBack(ans, candidates, target, 0, new ArrayList<Integer>(), 0);//遞歸開始，從下標(biāo)0元素開始 return ans; } private void checkBack(List<List<Integer>> ans, int[] candidates, int target, int index, List<Integer> combination, int sum) { if(target == sum) {//當(dāng)值已是target ans.add(combination); } else if(target > sum) { for(int i = index; i < candidates.length && sum + candidates[i] <= target; i++) {//當(dāng)前下標(biāo)不越界且加上sum不大于target List<Integer> tcom = new ArrayList<>(combination);//new一個(gè)新的組合結(jié)果 tcom.add(candidates[i]);//添加當(dāng)前的下標(biāo)元素 checkBack(ans, candidates, target, i, tcom, sum + candidates[i]);//下次遞歸時(shí)霹琼，數(shù)組循環(huán)從當(dāng)前下標(biāo)開始刷允，前面的元素?zé)o需重復(fù)選取，否則將出現(xiàn)重復(fù)的組合 } } } }
三碧囊、組合總和 II
-
題目條件
- 數(shù)組
candidates存在重復(fù)的元素 - 數(shù)組
candidates中的元素在每個(gè)組合中只能使用一次 - 組合不能重復(fù)
- 數(shù)組
candidates并非一定升序
- 數(shù)組
-
思路：
- 先將數(shù)組
candidates升序排列 - 遞歸回溯處理
- 循環(huán)數(shù)組的每個(gè)元素树灶，同時(shí)當(dāng)下標(biāo)值 + 傳入sum 不大于target
- sum：上層遞歸的值總和，也是傳入combination的值總和
- 當(dāng)前下標(biāo)在memory中值為0：未被訪問糯而，可作為組合一部分
- 然后將該下標(biāo)在memory記錄為已使用天通、同時(shí)添加到隊(duì)列
- 隊(duì)列的作用：記錄這一層遞歸中循環(huán)使用了的元素，循環(huán)結(jié)束才可將這些元素在memory中標(biāo)記為未被使用的初始狀態(tài)
- 為什么：在下一層循環(huán)中熄驼，不能重復(fù)使用已在組合內(nèi)的元素像寒；同一層循環(huán)內(nèi)：不能使用前面構(gòu)成的組合的元素
- 保證不重復(fù)組合的關(guān)鍵
- 調(diào)用函數(shù)遞歸
- 由于存在重復(fù)元素，不需要再次使用構(gòu)成數(shù)組
- 改變下標(biāo)瓜贾、記錄memory诺祸、queue內(nèi)即可
- 循環(huán)訪問數(shù)組元素結(jié)束：循環(huán)queue，改變memory值
- 循環(huán)數(shù)組的每個(gè)元素树灶，同時(shí)當(dāng)下標(biāo)值 + 傳入sum 不大于target
- 當(dāng)target = sum祭芦，得到一個(gè)組合結(jié)果筷笨，添加到結(jié)果集合
- 先將數(shù)組
class Solution { public List<List<Integer>> combinationSum2(int[] candidates, int target) { Arrays.sort(candidates);//排序數(shù)組 List<List<Integer>> ans = new ArrayList<>(); checkBack(ans, candidates, target, new int[candidates.length], new ArrayList<Integer>(), 0); return ans; } private void checkBack(List<List<Integer>> ans, int[] candidates, int target, int[] memory, List<Integer> combination, int sum) { if(target == sum) {//是一個(gè)組合結(jié)果，加入到結(jié)果集合 ans.add(combination); } else if(target > sum) { Queue<Integer> queue = new LinkedList<>();//記錄循環(huán)中被標(biāo)記已訪問的下標(biāo) for(int i = 0; i < candidates.length && sum + candidates[i] <= target; i++) { if(memory[i] == 0) {//未被訪問 memory[i] = 1;//標(biāo)記是組合一部分 queue.offer(i);//入隊(duì) List<Integer> tcom = new ArrayList<>(combination); tcom.add(candidates[i]);//構(gòu)造新組合 checkBack(ans, candidates, target, memory, tcom, sum + candidates[i]); while(i < candidates.length - 1 && candidates[i] == candidates[i + 1]) {//將下標(biāo)指向不重復(fù)的元素龟劲，同時(shí)也要標(biāo)記這些重復(fù)元素被使用（假使用胃夏，也即是不能用） i++; memory[i] = 1; queue.offer(i); } } } while(!queue.isEmpty()) {//恢復(fù)元素的可用性 memory[queue.poll()] = 0; } } } }-
改進(jìn)：
因?yàn)閿?shù)組已排序
使用下標(biāo)變化可達(dá)到標(biāo)記效果
-
調(diào)用函數(shù)傳入當(dāng)前下標(biāo) 加 1 值，作為下一層遞歸中昌跌，循環(huán)開始的下標(biāo)
- 將不會(huì)存在重復(fù)訪問元素的情況
- 構(gòu)造組合的元素不會(huì)在數(shù)組中重復(fù)選取
class Solution { public List<List<Integer>> combinationSum2(int[] candidates, int target) { Arrays.sort(candidates); List<List<Integer>> ans = new ArrayList<>(); checkBack(ans, candidates, target, 0, new ArrayList<Integer>(), 0); return ans; } private void checkBack(List<List<Integer>> ans, int[] candidates, int target, int index, List<Integer> combination, int sum) { if(target == sum) { ans.add(combination); } else if(target > sum) { for(int i = index; i < candidates.length && sum + candidates[i] <= target; i++) { List<Integer> tcom = new ArrayList<>(combination); tcom.add(candidates[i]); checkBack(ans, candidates, target, i + 1, tcom, sum + candidates[i]); while(i < candidates.length - 1 && candidates[i] == candidates[i + 1]) {//將下標(biāo)指向不重復(fù)的元素 i++; } } } } }
