我的解法都不靠近回溯思想😕
单纯记录下这能有的解法，以后深入理解回溯回头看看🧐
一、组合
递归、DFS
n选k个的组合
n必须大于k
- 递归条件
- 结束：k=1，将n选1，添加到结果列表中
- 递归调用：k大于1，循环调用自己（n-1，k-1）
- 调用返回后：结果列表ans尾部添加了（n-1，k-1）的结果，这次调用添加的结果每个都要加上n，因为在该次函数中，是n选k，那么需要从队列尾部中开始遍历长度为k-1 的结果加上n
例如：4 选 3
例如：5 选 3的循环：
- n = 5，k = 3
- 调用函数：4 选 2 的循环开始：
- n = 4， k = 2
- 第一次循环：3 选 1：ans = [[1], [2], [3]]
- 调用结束，返回，处理后：ans = [[1,4], [2,4], [3,4]]
- n = 3， k = 2
- 第二次循环：2 选 1：ans = [[1,4], [2,4], [3,4], [1], [2]]
- 调用结束，返回，处理后：ans = [[1,4], [2,4], [3,4], [1,3], [2,3]]
- n = 2， k = 2
- 第三次循环：1 选 1：ans = [[1,4], [2,4], [3,4], [1,3], [2,3], [1]]
- 调用结束，返回，处理后：ans = [[1,4], [2,4], [3,4], [1,3], [2,3], [1,2]]
- n = 1
- 第四次循环：0 选 1，函数调用结束
- n = 0，退出循环
- 4 选 2 调用返回：ans = [[1,4], [2,4], [3,4], [1,3], [2,3], [1,2]]
- 处理ans得：ans = [[1,4,5], [2,4,5], [3,4,5], [1,3,5], [2,3,5], [1,2,5]]
- n = 4，下一次循环
- 调用函数：3 选 2
- n = 3， k = 2
- 第一次循环：调用函数：2 选 1
- 调用结束返回：ans = [[1,4,5], [2,4,5], [3,4,5], [1,3,5], [2,3,5], [1,2,5], [1], [2]]
- 处理：ans = [[1,4,5], [2,4,5], [3,4,5], [1,3,5], [2,3,5], [1,2,5], [1,3], [2,3]]
- n = 2， k = 2
- 第二次循环：调用函数 1 选 1
- 调用结束返回：ans = [[1,4,5], [2,4,5], [3,4,5], [1,3,5], [2,3,5], [1,2,5], [1,3], [2,3], [1]]
- 处理：ans = [[1,4,5], [2,4,5], [3,4,5], [1,3,5], [2,3,5], [1,2,5], [1,3], [2,3], [1,2]]
- n=1
- 第三次循环：调用函数 0 选 1：调用结束
- n=0，结束循环
- 返回：ans = [[1,4,5], [2,4,5], [3,4,5], [1,3,5], [2,3,5], [1,2,5], [1,3], [2,3], [1,2]]
- 处理：ans = [[1,4,5], [2,4,5], [3,4,5], [1,3,5], [2,3,5], [1,2,5], [1,3,4], [2,3,4], [1,2,4]]
- n = 3，下一次循环
- 调用函数：2 选 2
- n = 2, ， k = 2
- 第一次循环：调用函数 1 选 1
- 返回：ans = [[1,4,5], [2,4,5], [3,4,5], [1,3,5], [2,3,5], [1,2,5], [1,3,4], [2,3,4], [1,2,4], [1]].
- 处理：ans = [[1,4,5], [2,4,5], [3,4,5], [1,3,5], [2,3,5], [1,2,5], [1,3,4], [2,3,4], [1,2,4], [1,2]]
- n = 1
- 第二次循环：0选1 函数调用结束
- n = 0 结束循环
- 返回 ans = [[1,4,5], [2,4,5], [3,4,5], [1,3,5], [2,3,5], [1,2,5], [1,3,4], [2,3,4], [1,2,4], [1,2]]
- 处理：ans = [[1,4,5], [2,4,5], [3,4,5], [1,3,5], [2,3,5], [1,2,5], [1,3,4], [2,3,4], [1,2,4], [1,2,3]]
- n = 2， k = 2
- 调用函数 ：1选2返回
- n = 1， k = 2
- 调用函数：0 选 2 返回
- n = 0 ，退出循环
class Solution {
private List<List<Integer>> ans = new ArrayList<>();
public List<List<Integer>> combine(int n, int k) {
if(n >= k) {
if(k == 1) {
for(int i = n; i > 0; i--) {
List<Integer> temp = new ArrayList<Integer>();
temp.add(i);
ans.add(temp);//在列表最后面追加新组合的数字
}
} else {
while(n > 0 && k > 1) {
combine(n - 1, k - 1);//循环调用
for(int i = ans.size() - 1; i >= 0; i--) {//将n加入，是为新组合
List<Integer> temp = ans.get(i);
if(temp.size() == k - 1) {
temp.add(n);
} else {
i = -1;//不是 k - 1 个数，说明不是新组合，不处理前面的，赋值-1退出循环；虽然break就行，但这样更好
}
}
--n;
}
}
}
return ans;
}
}
上述解法比较一般
学习回溯与剪枝：回溯算法 + 剪枝（Java） - 组合 - 力扣（LeetCode） (leetcode-cn.com)
二、全排列
循环遍历组织答案
1 <= nums.length <= 6：数组不为空
思路：第一个数字直接入列表
外循环：循环数组从第二个数字开始
内循环：循环列表，组织新的全排列
组织：根据temp在其 size + 1 个位置添加上数组的 第 i 个元素，从而产生 size + 1 个结果存放到ans
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> ans = new ArrayList<>();
List<Integer> temp = new ArrayList<>();//暂存ans的元素
temp.add(nums[0]);
ans.add(temp);
for(int i = 1; i < nums.length; i++) {
int j = ans.size() - 1;//未开始循环（上一次循环的ans结果长度），-1作为下标，从后面开始获取
while(j >= 0) {
temp = ans.remove(j--);//删去下标为j的元素，返回给temp暂存，j自减
for(int k = 0; k <= temp.size(); k++) {//根据temp的长度size，一共有size + 1 个位置插入 num[i]
List<Integer> t = new ArrayList<>(temp);
t.add(k, nums[i]);//将指定元素插入此列表中的指定位置
ans.add(t);
}
}
}
return ans;
}
}
相似的题： 全排列 II
不同的是：数组有重复数字，那么组织过程可能会产生重复的排列，需要判断才能添加
class Solution { public List<List<Integer>> permuteUnique(int[] nums) { List<List<Integer>> ans = new ArrayList<>(); List<Integer> temp = new ArrayList<>(); temp.add(nums[0]); ans.add(temp); for(int i = 1; i < nums.length; i++) { int j = ans.size() - 1; while(j >= 0) { temp = ans.remove(j--); for(int k = 0; k <= temp.size(); k++) { List<Integer> t = new ArrayList<>(temp); t.add(k, nums[i]); if(!ans.contains(t)) { ans.add(t); } } } } return ans; } }
学习回溯：回溯算法入门级详解 + 练习
三、字母大小写全排列
将字符串添加到列表
遍历字符串
如果当前下标是字母就遍历列表中已有的所有的字符串，将当前下标的字母转换大小写再添加到队列
下标自增
class Solution {
private static final int DV = 'a' - 'A';//difference value
public List<String> letterCasePermutation(String s) {
List<String> ans = new ArrayList<String>();
ans.add(s);
for(int i = 0; i < s.length(); i++) {
int flag = -1;
if((flag = checkUpperOrLower(s.charAt(i))) != -1) {
int size = ans.size();
if(flag == 0) {//是小写字母，转大写
while(size > 0) {
char[] sarry = ans.get(--size).toCharArray();
sarry[i] = (char)(sarry[i] - DV);//int向下转型char，需要强制转换
ans.add(new String(sarry));
}
} else {//是大小字母，转小写
while(size > 0) {
char[] sarry = ans.get(--size).toCharArray();
sarry[i] = (char)(sarry[i] + DV);//int向下转型char，需要强制转换
ans.add(new String(sarry));
}
}
}
}
return ans;
}
private int checkUpperOrLower(char t) {
if(t >= 'a' && t <= 'z') {//是小写字母
return 0;
} else if(t >= 'A' && t <= 'Z') {//是大小字母
return 1;
}
return -1;//is number
}
}
