在形式上,最明显的问题就是[1,2]和[2,1]这两个list在排列中是正确的,而在组合中一般只有前者
排列回溯注重元素的顺序,并且允许重复元素的出现,而组合回溯则不考虑元素的顺序。
排列回溯:
通常使用一个 boolean
数组来标记哪些元素已经被选择,哪些尚未被选择
在递归的每一层,我们都尝试选择一个尚未被选择的元素,并继续递归
for (int i = 0; i < nums.length; i++) { if (!used[i]) { used[i] = true; permutation.add(nums[i]); backtrackPermute(nums, permutation, used, result); permutation.remove(permutation.size() - 1); used[i] = false; } }
组合回溯:
通常使用一个参数startIndex来记录当前开始选择元素的位置,以确保不会重复选择之前已经选择过的元素。
for (int i = startIndex; i <= n; i++) { combination.add(i); backtrackCombine(n, k, i + 1, combination, result); combination.remove(combination.size() - 1); }
这里为什么是i+1而不是startIndex+1:我们需要保证每次递归调用时,上一层递归的元素不会再被选择,startIndex表示当前递归层次开始选择的元素,而i则表示当前循环选择的元素。
标签:排列,组合,递归,元素,选择,startIndex,used,回溯 From: https://www.cnblogs.com/kun1790051360/p/18076267