Summary
回溯算法中的排列与组合
框架模板
回溯算法在解决排列和组合问题时，两者的主要区别在于元素的顺序是否重要，以及结果中是否允许重复选取相同元素。
- 排列 (Permutation)
- 顺序重要：在排列中，元素的顺序会影响结果。例如，[1, 2] 和 [2, 1] 被视为不同的排列。
- 典型问题：求数组的全排列、给定数列的不同排列方式等。
- 特点：需要考虑每个元素在每个位置的可能性，通常通过标记来避免重复选取已使用的元素。
- 组合 (Combination)
- 顺序不重要：在组合中，元素的顺序不影响结果。例如，[1, 2] 和 [2, 1] 被视为相同的组合。
- 典型问题：求数组的所有子集、选出若干个元素的组合等。
- 特点：只需要关心某个元素是否被选中，不需要考虑顺序，通常可以通过限制递归的起始位置来避免重复组合。
排列代码模板
void backtrack(List<List<Integer>> res, List<Integer> tempList, int[] nums, boolean[] used) {
if (tempList.size() == nums.length) {
res.add(new ArrayList<>(tempList));
} else {
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue; // 跳过已使用的元素
used[i] = true;
tempList.add(nums[i]);
backtrack(res, tempList, nums, used);
used[i] = false;
tempList.remove(tempList.size() - 1);
}
}
}
组合框架模板
void backtrack(List<List<Integer>> res, List<Integer> tempList, int[] nums, int start) {
res.add(new ArrayList<>(tempList));
for (int i = start; i < nums.length; i++) {
tempList.add(nums[i]);
backtrack(res, tempList, nums, i + 1); // 从下一个元素开始
tempList.remove(tempList.size() - 1);
}
}
- 排列中元素的顺序重要，通常使用一个 boolean[] used 数组来跟踪已选择的元素。
- 组合中元素的顺序不重要，使用 start 参数控制递归的起始位置，以避免重复的组合。
解题
class Solution {
private List<List<Integer>> res;
private List<Integer> tmp;
public List<List<Integer>> permute(int[] nums) {
res = new ArrayList<>();
tmp = new ArrayList<>();
int n = nums.length;
boolean[] used = new boolean[n];
backtrack(n,nums,used);
return res;
}
private void backtrack(int n ,int[] nums,boolean[] used){
if(tmp.size() == n){
res.add(new ArrayList<>(tmp));
}
for(int i = 0 ; i < nums.length; i++){
if(!used[i]){
used[i] = true;
tmp.add(nums[i]);
backtrack(n,nums,used);
used[i] = false;
tmp.remove(tmp.size()-1);
}
}
}
}
class Solution {
private List<List<Integer>> res;
private List<Integer> tmp;
public List<List<Integer>> combine(int n, int k) {
res = new ArrayList<>();
tmp = new ArrayList<>();
backtrack(n,k,1);
return res;
}
private void backtrack(int n , int k ,int start){
//剪枝操作
if(tmp.size() + (n-start+1) < k){
return;
}
if(tmp.size() == k){
res.add(new ArrayList<>(tmp));
}
for(int i = start ; i <= n ; i++){
tmp.add(i);
backtrack(n,k,i+1);
tmp.remove(tmp.size() - 1);
}
}
}
class Solution {
private List<Integer> path;
private List<List<Integer>> res;
public List<List<Integer>> combinationSum3(int k, int n) {
path = new ArrayList<>();
res = new ArrayList<>();
backtrack(k,n,1,0);
return res;
}
private void backtrack( int k , int n,int cur, int sum ){
if (sum > n) { // 剪枝操作
return;
}
if(path.size() == k && sum == n){
res.add(new ArrayList<>(path));
}
for(int i = cur ; i <= 9 - (k-path.size()) + 1; i++){
path.add(i);
backtrack(k,n,i+1,sum + i);
path.remove(path.size()-1);
}
}
}