模版
// 结果集合
public List<List<Integer>> res = new ArrayList<>();
// 路径集合
public LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> model(int[] nums) {
// 根据是否需要指定开始位置进行传参
backtracking(nums,0);
return res;
}
public void backtracking(int []nums,int index){
// 根据结果叶子节点还是节点进行结果收集
res.add(new ArrayList<>(path));
//根据 是否需要依赖上一位置进行遍历
for(int i=index;i<nums.length;i++){
path.add(nums[i]);
backtracking(nums,i+1);
path.removeLast();
}
}
分类
（1） 元素无重复不可复选
即 nums 中的元素都是唯一的，每个元素最多只能被使用一次
子集（元素无重不可复选）
输入一个无重复元素的数组 nums，其中每个元素最多使用一次，请你返回 nums 的所有子集。
组合（元素无重不可复选）
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
大小为
k的组合就是大小为k的子集
排列（元素无重不可复选）
给定一个不含重复数字的数组 nums，返回其所有可能的全排列
（2） 元素可重复不可复选
即 nums 中的元素可以存在重复，每个元素最多只能被使用一次
子集/组合（元素可重不可复选）
给你一个整数数组 nums，其中可能包含重复元素，请你返回该数组所有可能的子集
排列（元素可重不可复选）
（3） 元素无重可复选
即 nums 中的元素都是唯一的，每个元素可以被使用若干次
子集/组合 （元素无重可复选）
排列（元素无重可复选）
1. 待选元素互不相同，且不可重复选择
1.1 子集（元素无重不可复选）
数组元素互不相同，所以不需要考虑去重的问题
==子集==收集的结果应该是递归树中的==每一个节点==，所以在进入回溯函数之后就直接收集结果
public List<List<Integer>> res = new ArrayList<>();
public LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> subsets(int[] nums) {
backtracking(nums,0);
return res;
}
public void show(int []nums,int index){
res.add(new ArrayList<>(path));
for(int i=index;i<nums.length;i++){
path.add(nums[i]);
backtracking(nums,i+1);
path.removeLast();
}
}
1.2 组合（元素无重不可复选）
相当于是子集问题
给你输入一个数组
nums = [1,2..,n]和一个正整数k，请你生成所有大小为k的子集
==相当于收集第k层的节点==
class Solution {
public List<List<Integer>> res = new ArrayList<>();
public LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> combine(int n, int k) {
back(n,k,1);
return res;
}
public void back(int n,int k,int index){
// 收集第 k 层上的节点
if(path.size()==k){
res.add(new ArrayList<>(path));
}
for(int i=index;i<=n;i++){
path.add(i);
back(n,k,i+1);
path.removeLast();
}
}
}
1.3 排列（元素无重不可复选）
收集所有叶节点的结果集合
class Solution {
List<List<Integer>> result = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> permute(int[] nums) {
if (nums.length == 0) return result;
backtrack(nums, path);
return result;
}
public void backtrack(int[] nums, LinkedList<Integer> path) {
if (path.size() == nums.length) {
result.add(new ArrayList<>(path));
}
for (int i =0; i < nums.length; i++) {
// 如果path中已有，则跳过
if (path.contains(nums[i])) {
continue;
}
path.add(nums[i]);
backtrack(nums, path);
path.removeLast();
}
}
}
2. 元素可重复不可复选
2.1 子集（元素可重不可复选）
可能包含重复元素，需要进行去重处理
借助卡哥的图翻译翻译：
可以使用一个标记数组来判断待选集合中每个元素是否被使用过，
以【1，2，2】 为例子
最左边的遍历会产生【】、【1】、【1，2】、【1，2，2】 这四个集合
在【1，2，2】 产生之后会往上回溯，先回溯到集合为【1，2】，因为没有新的元素可以使用，再回溯到集合中只有【1】
此时第一个2已经使用过，而唯一可以选的元素的值也是2，需要跳过
对应下面代码中的
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1]==true)
continue;
它的意思是，如果当前待选元素与前一个元素相等，且前一个元素已经使用过了，那么这条分支就不应该继续往下走，因为前面已经走过了，所以continue，继续当前位置的 的 下一个元素的选择。
代码：
class Solution {
List<List<Integer>> result = new ArrayList<>();// 存放符合条件结果的集合
LinkedList<Integer> path = new LinkedList<>();// 用来存放符合条件结果
boolean[] used;
public List<List<Integer>> subsetsWithDup(int[] nums) {
if (nums.length == 0){
result.add(path);
return result;
}
Arrays.sort(nums);
used = new boolean[nums.length];
subsetsWithDupHelper(nums, 0);
return result;
}
private void subsetsWithDupHelper(int[] nums, int startIndex){
result.add(new ArrayList<>(path));
if (startIndex >= nums.length){
return;
}
for (int i = startIndex; i < nums.length; i++){
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1]==true){
continue;
}
path.add(nums[i]);
used[i] = true;
subsetsWithDupHelper(nums, i + 1);
path.removeLast();
used[i] = false;
}
}
}
优化：
如果当前选择的元素大于了开始选择的位置
且这个数字和它前面的数字一样，那就跳过
因为在选择这个元素之前，一定选择过了之前的和它相等的元素，（i>start）
if(i>start && nums[i-1]==nums[i])continue;
完整代码：
List<List<Integer>> res = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
subsetsWithDupHelper(nums,0);
return res;
}
private void subsetsWithDupHelper( int[] nums, int start ) {
res.add( new ArrayList<>(path) );
for ( int i = start;i<nums.length;i++ ){
if(i>start && nums[i-1]==nums[i])continue;
path.add( nums[i] );
subsetsWithDupHelper( nums,i+1 );
path.removeLast();
}
}
2.2 组合问题（元素可重不可复选）
换个问法就变成子集问题了：请你计算
candidates中所有和为target的子集。
class Solution {
private List<List<Integer>> res = new ArrayList<>();
private LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
back(candidates,target,0,0);
return res;
}
private void back(int[] candidates,int target,int index,int sum){
if(sum==target){
res.add(new ArrayList<>(path));
}
for(int i=index;i<candidates.length;i++){
if(sum+candidates[i]>target ){
return;
}
if( i>index && candidates[i]==candidates[i-1] ){
continue ;
}
sum+=candidates[i];
path.add(candidates[i]);
back(candidates,target,i+1,sum);
path.removeLast();
sum-=candidates[i];
}
}
}
2.3 排列（元素可重不可负复选）
因为包含了重复元素，需要去重
【2，1（a），1（b）】或【2，1（b），1（a）】只能出现一个
交换律告诉我们，对于全排列，只要数组的元素一样，那么最后的全排列结果集合一定是一样的
为了方便判断元素是否使用过，所以先对数组排序。
和之前的去重一样，在同一层上，只允许相同值的元素使用一次
if ( i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false )
continue;
//结果集合
List<List<Integer>> res = new ArrayList<>();
//路径集合
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> permuteUnique( int[] nums ) {
Arrays.sort(nums);
boolean[] used = new boolean[nums.length];
getPermute( nums, used, 0 );
return res;
}
private void getPermute( int[] nums, boolean[] used, int start ) {
if ( path.size() == nums.length ) {
res.add( new ArrayList<>( path ) );
return;
}
for ( int i = 0; i < nums.length; i++ ) {
// 当前元素与前一个元素相同，且前一个元素使用过
if ( i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false ) {
continue;
}
if ( used[i] == false ) {
used[i] = true;
path.add( nums[i] );
getPermute( nums, used, i + 1 );
path.removeLast();
used[i] = false;
}
}
}
}
这里不能直接使用 i>start的去重是因为之前是组合问题，需要从下一个元素开始，但全排列是要求所有元素都使用到。
3. 元素无重可复选
3.1 子集/组合（元素无重可复选）
说是组合问题，实际上也是子集问题：
candidates的哪些子集的和为target？
class Solution {
private List<List<Integer>> res = new ArrayList<>();
private LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
back(candidates,target,0,0);
return res;
}
private void back(int[]candidates,int target,int index,int sum){
if(sum==target){
res.add(new ArrayList<>(path));
return;
}
if(sum>target)return;
// 从index 开始，不会往前找
for(int i=index;i<candidates.length;i++){
if(sum+candidates[i]>target)continue;
sum+=candidates[i];
path.add(candidates[i]);
back(candidates,target,i,sum);
path.removeLast();
sum-=candidates[i];
}
}
}
3.2 排列（元素无重可复选）
nums 数组中的元素无重复且可复选的情况下，有哪些排列？
输入 nums = [1,2,3]，那么这种条件下的全排列共有 3^3 = 27 种：
[
[1,1,1],[1,1,2],[1,1,3],[1,2,1],[1,2,2],[1,2,3],[1,3,1],[1,3,2],[1,3,3],
[2,1,1],[2,1,2],[2,1,3],[2,2,1],[2,2,2],[2,2,3],[2,3,1],[2,3,2],[2,3,3],
[3,1,1],[3,1,2],[3,1,3],[3,2,1],[3,2,2],[3,2,3],[3,3,1],[3,3,2],[3,3,3]
]
直接无需去重
List<List<Integer>> res = new LinkedList<>();
LinkedList<Integer> track = new LinkedList<>();
public List<List<Integer>> permuteRepeat(int[] nums) {
backtrack(nums);
return res;
}
// 回溯算法核心函数
void backtrack(int[] nums) {
// base case，到达叶子节点
if (track.size() == nums.length) {
// 收集叶子节点上的值
res.add(new LinkedList(track));
return;
}
// 回溯算法标准框架
for (int i = 0; i < nums.length; i++) {
// 做选择
track.add(nums[i]);
// 进入下一层回溯树
backtrack(nums);
// 取消选择
track.removeLast();
}
}
待选元素可能相同--且有附加要求
题目要求所有递增的子序列，且不能重复
🌰 【4，6，7（a），7（b）】 字母是为了标识相同元素
结果中可以有【4，7（a）】或 【4、7（b）】 但不能两个同时存在
借助卡哥的图分析分析：
从绿色箭头往下递归前，建立map统计当前元素为开始时的使用情况，
最左边【4，7】 已经使用过一次 7
当蓝色箭头开始往下递归时，map中已经记录过7使用过，也就是以4开头，第二位置的元素使用过7，不能继续往下递归了，continue 之后继续选择下一个可以使用的元素。
关于数层去重与树枝去重，推荐看原文 ：代码随想录-全排列
修订记录
2022-09-15 19:47:13 整理题型