【= 组合 =】
题目描述
解题思路
求得n个数中k个数的组合集合
关于题解 可以参考这个
🙃🙃🙃 关于回溯算法 你该了解这些！！！
解题方法
- PHP
function combine($n, $k) {
$result = [];
$this->backtrack($n,$k,1,[], $result);
return $result;
}
function backtrack($n,$k,$start,$path,&$result) {
if(count($path) == $k) {
$result[] = $path;
return;
}
//剪枝：如果循环起始位置之后的个数已经不满足我们需要的个数了
//就没必要在继续检索了，减少不必要的循环
for ($i=$start;$i<=$n-($k-count($path))+1;$i++) {
$path[] = $i;
$this->backtrack($n,$k,$i+1,$path,$result);
array_pop($path);
}
}
- GO
var res [][]int
func combine(n int, k int) [][]int {
res = [][]int{}
backtrack(n, k, 1, []int{})
return res
}
func backtrack(n, k, start int, path []int) {
if len(path) == k {
temp := make([]int, k)
copy(temp, path)
res = append(res, temp)
return
}
for i := start; i <= n-(k-len(path))+1; i++ {
path = append(path, i)
backtrack(n, k, i+1, path)
path = path[:len(path)-1]
}
}
[= 全排列 =]
题目描述
解题思路
经典回溯算法题：相较于上题较简单
回溯中参数为原始数组nums，以及当前数组arr
回溯的终止条件为，当前arr的个数已经等于原始数组nums
回溯的处理，循环遍历原始数组nums,当前值不存在arr中时，将该值放入arr中，递归调用
由于上面的行为会找到最终答案，所以，在处理完上面请求时，将arr进行出栈操作，继续遍历
解题方法
- PHP
function permute($nums) {
$res = [];
$this->backtrack($nums,[],$res);
return $res;
}
function backtrack($nums, $arr, &$res) {
if(count($arr) == count($nums)) {
$res[] = $arr;
return;
}
foreach($nums as $v) {
if(!in_array($v,$arr)) {
$arr[] = $v;
$this->backtrack($nums, $arr, $res);
array_pop($arr);
}
}
}
- GO
var res [][]int
func permute(nums []int) [][]int {
res = [][]int{}
backtrack(nums,len(nums), []int{})
return res
}
func backtrack(nums[]int, numLen int, path []int) {
if len(nums)==0{
temp := make([]int, len(path))
copy(temp, path)
res = append(res, temp)
return
}
for i:=0;i<numLen;i++ {
cur :=nums[i]
path = append(path,cur)
nums = append(nums[:i],nums[i+1:]...)
backtrack(nums, len(nums), path)
nums = append(nums[:i], append([]int{cur},nums[i:]...)...)
path = path[:len(path)-1]
}
}
