导读:最近做了几道LeetCode的回溯问题,有点体会,在此记录防止遗忘。
要点:进入新一层递归刷新状态,递归退出时状态恢复。
描述:此题给出了一个不含重复元素的数组,要求输出该数组的所有字典序全排列。
分析:以 [1,2,3] 为例,画出决策树如下:
其中,虚线 部分表示剪枝操作,第三层递归的剪枝省略。
Java代码:
xxxxxxxxxx
class Solution {
public List<List<Integer>> permute(int[] nums) {
//排序非常重要,因为要按照字典序输出,将数组从小到大排列便于操作
Arrays.sort(nums);
//输出List
List<List<Integer>> li = new ArrayList<List<Integer>>();
//状态存储List
LinkedList<Integer> tmpli = new LinkedList<Integer>();
//为了确保前一层使用的数字不能被下一层递归使用,应使用一个额外数组存放数字使用情况
int[] check = new int[nums.length];
Arrays.fill(check, 0);
recursive(nums, li, tmpli, check);
return li;
}
void recursive(int[] nums, List<List<Integer>> li, LinkedList<Integer> tmpli, int[] check){
//递归出口:如果暂存List的数字达到三个,说明是一个全排列,此时将其深复制一份放进结果List中
if(tmpli.size() == nums.length) {
li.add(new ArrayList<Integer>(tmpli));
return;
} else {
//递归主体
for(int i=0; i<nums.length; i++){
if(check[i]==0){
//状态进入
check[i]=1;
tmpli.add(nums[i]);
//递归
recursive(nums, li, tmpli, check);
//状态退出
tmpli.removeLast();
check[i]=0;
}
}
}
}
}
描述: 此题与上一题的区别在于给出的数组含有重复元素,仍要求给出字典序全排列。
分析:除了保留上一题的剪枝方法,由于重复元素的使用会导致结果集重复(例如 [1,1,2],如果按原有剪枝策略,第二个1仍会被记录到 tmpli
中),因此要修改剪枝策略。
Java代码:
xxxxxxxxxx
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> li = new ArrayList<List<Integer>>();
LinkedList<Integer> tmpli = new LinkedList<Integer>();
int[] check = new int[nums.length];
Arrays.sort(nums);
Arrays.fill(check, 0);
backTrace(li, nums, check, tmpli);
return li;
}
void backTrace(List<List<Integer>> li, int[] nums, int[] check, LinkedList<Integer> tmpli) {
//递归出口
if(tmpli.size() == nums.length) {
li.add(new ArrayList<Integer>(tmpli));
return;
}
//递归主体
for(int i=0; i<nums.length; i++) {
//新的剪枝:
//如果是同一层,且非第一次出现的,且能使用的数字,则直接跳过
//增加check[i-1]==0:
//保证前一个元素在当前层仍可用
if(i>0 && nums[i]==nums[i-1] && check[i-1]==0){
continue;
}
if(check[i]==0){
//状态刷新
check[i] = 1;
tmpli.add(nums[i]);
//递归
backTrace(li, nums, check, tmpli);
//状态恢复
tmpli.removeLast();
check[i] = 0;
}
}
return;
}
}
描述: 给出一个数组和目标值,要求给出数组中总和为目标值的所有组合,元素可以重复使用。
分析:尝试逐级递减,递归出口条件为减少至0或为负数。为了不产生重复的结果集,先对数组排序,且每次选取的元素不能超过上一次选取的值。
Java代码:
xxxxxxxxxx
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> li = new ArrayList<List<Integer>>();
Arrays.sort(candidates);
recursive(li, candidates, target, candidates.length, new LinkedList<Integer>());
return li;
}
void recursive(List<List<Integer>> li, int[] candidates, int residue, int len, LinkedList<Integer> tmpli) {
//递归出口
if(residue == 0){
li.add(new ArrayList<Integer>(tmpli));
return;
}
//引入len防止选取的值超过上一层递归的取值
for(int i=0; i<len; i++){
if(residue-candidates[i] >= 0){
//状态进入
tmpli.add(candidates[i]);
//递归
recursive(li, candidates, residue-candidates[i], i+1, tmpli);
//状态退出
tmpli.removeLast();
} else {
return;
}
}
}
}
描述:与上一题类似,但不允许使用重复的值(数组中会给出多个重复值,每个值只能用一次,如[1,1,2])。
分析:大致与上一题类似,但每一层不允许使用重复元素,可以参考47题的剪枝,但又为了防止重复解,其剪枝方式有点不同。
Java代码:
xxxxxxxxxx
class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> li = new ArrayList<List<Integer>>();
Arrays.sort(candidates);
int[] check = new int[candidates.length];
Arrays.fill(check, 0);
recursive(li, candidates, target, candidates.length, new LinkedList<Integer>(), check);
return li;
}
void recursive(List<List<Integer>> li, int[] candidates, int residue, int len, LinkedList<Integer> tmpli, int[] check) {
//递归出口
if(residue == 0){
li.add(new ArrayList<Integer>(tmpli));
return;
}
for(int i=0; i<len; i++){
//剪枝,不能使用上级递归已经用过的元素
if(check[i] == 1) {
continue;
}
//剪枝,同一级不能使用重复的元素,不然导致结果集重复
if(i>0 && check[i-1]==0 && candidates[i]==candidates[i-1]){
continue;
}
//递归主体
if(residue-candidates[i] >= 0){
//找到相同元素中的最后一个,防止下一层递归时,有元素被漏掉
//(因为元素从小到大排列,满足条件的元素必然是有序数组中所有相同元素的第一个,
// 传递截止值i会把后面相同的元素直接排除,下一级递归无法使用,导致漏解,且这样
// 做还能加快for的进行速度)
while(i<len-1 && candidates[i+1] == candidates[i]){
i++;
}
tmpli.add(candidates[i]);
check[i] = 1;
recursive(li, candidates, residue-candidates[i], i, tmpli, check);
check[i] = 0;
tmpli.removeLast();
} else {
//因为是从小到大尝试,所以出现负数说明尝试的数字太大了,不必要继续尝试
return;
}
}
return;
}
}