一、全排列 II
- 递归过程就像二叉树，每一层递归结束后（回溯），看情况清理枝叶
- 递归函数结束条件：当传入的排列结果长度等于数组长度
- 递归函数执行：
- 循环数组查找，当该元素未被访问
- 将其标记被访问，是排列的一部分
- 然后加入排列结果中（至于new的原因：传入的排列可能会有很多新的相关排列，也即是非叶结点）
- 接着调用递归函数，再次组成排列结果
- 函数返回后（回溯）：判断目前这个元素在数组中是否重复
- 重复是不需要再用来构造排序的
- 因为数组是被排序过了，所以循环遍历，直到越界或者不等于
- 该元素要被重新标记为未加入排列，因为可以在下一个元素的下一层递归中，构建出新的排列
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
Arrays.sort(nums);//数组排序
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++) {//遍历数组
if(memory[i] == 0) {//到当前递归，数组中的值不在当前传入permute中
memory[i] = 1;//现在在了
List<Integer> tpermute = new ArrayList<>(permute);
tpermute.add(nums[i]);
checkBack(nums, memory, ans, tpermute);//进行下一层递归
memory[i] = 0;//递归结束就还未出现在往后构造的排列中
while(i < nums.length - 1 && nums[i] == nums[i + 1]) {//处理重复的排列元素，不需要重复的排列
i++;//即使最后一个还是重复的，当时在外循环中，i自增后判断结果越界，结束循环。递归结束
}
}
}
}
}
}
二、组合总和
-
题目条件
- 无重复元素
- candidates数组中的元素可无限制重复选取
- 数字值、数量不相等的组合就是唯一的
- 给定数组不一定按升序排列
-
思路：
- 类似二叉树
- 递归回溯处理
- 每次循环从下标index开始，保证前面的元素不再选取，因为哪些组合早已出现过
- index就是限制组合的重复构成
- 题目要求组合的元素在数组无限选取
- 循环数组开始就要有个index开始，防止重复
- 递归调用函数时，将组合sum值传入，提高效率
- 当sum和target相同，即可得到一个组合结果
- 递归的结束
- 循环的另一个条件sum + 当前 下标元素不大于target
- 否则结束循环，递归结束
- 数组需先排序，从而减少没必要的递归（值比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);//递归开始，从下标0元素开始 return ans; } private void checkBack(List<List<Integer>> ans, int[] candidates, int target, int index, List<Integer> combination, int sum) { if(target == sum) {//当值已是target ans.add(combination); } else if(target > sum) { for(int i = index; i < candidates.length && sum + candidates[i] <= target; i++) {//当前下标不越界且加上sum不大于target List<Integer> tcom = new ArrayList<>(combination);//new一个新的组合结果 tcom.add(candidates[i]);//添加当前的下标元素 checkBack(ans, candidates, target, i, tcom, sum + candidates[i]);//下次递归时，数组循环从当前下标开始，前面的元素无需重复选取，否则将出现重复的组合 } } } }
三、组合总和 II
-
题目条件
- 数组
candidates存在重复的元素 - 数组
candidates中的元素在每个组合中只能使用一次 - 组合不能重复
- 数组
candidates并非一定升序
- 数组
-
思路：
- 先将数组
candidates升序排列 - 递归回溯处理
- 循环数组的每个元素，同时当下标值 + 传入sum 不大于target
- sum：上层递归的值总和，也是传入combination的值总和
- 当前下标在memory中值为0：未被访问，可作为组合一部分
- 然后将该下标在memory记录为已使用、同时添加到队列
- 队列的作用：记录这一层递归中循环使用了的元素，循环结束才可将这些元素在memory中标记为未被使用的初始状态
- 为什么：在下一层循环中，不能重复使用已在组合内的元素；同一层循环内：不能使用前面构成的组合的元素
- 保证不重复组合的关键
- 调用函数递归
- 由于存在重复元素，不需要再次使用构成数组
- 改变下标、记录memory、queue内即可
- 循环访问数组元素结束：循环queue，改变memory值
- 循环数组的每个元素，同时当下标值 + 传入sum 不大于target
- 当target = sum，得到一个组合结果，添加到结果集合
- 先将数组
class Solution { public List<List<Integer>> combinationSum2(int[] candidates, int target) { Arrays.sort(candidates);//排序数组 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) {//是一个组合结果，加入到结果集合 ans.add(combination); } else if(target > sum) { Queue<Integer> queue = new LinkedList<>();//记录循环中被标记已访问的下标 for(int i = 0; i < candidates.length && sum + candidates[i] <= target; i++) { if(memory[i] == 0) {//未被访问 memory[i] = 1;//标记是组合一部分 queue.offer(i);//入队 List<Integer> tcom = new ArrayList<>(combination); tcom.add(candidates[i]);//构造新组合 checkBack(ans, candidates, target, memory, tcom, sum + candidates[i]); while(i < candidates.length - 1 && candidates[i] == candidates[i + 1]) {//将下标指向不重复的元素，同时也要标记这些重复元素被使用（假使用，也即是不能用） i++; memory[i] = 1; queue.offer(i); } } } while(!queue.isEmpty()) {//恢复元素的可用性 memory[queue.poll()] = 0; } } } }-
改进：
因为数组已排序
使用下标变化可达到标记效果
-
调用函数传入当前下标 加 1 值，作为下一层递归中，循环开始的下标
- 将不会存在重复访问元素的情况
- 构造组合的元素不会在数组中重复选取
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]) {//将下标指向不重复的元素 i++; } } } } }
