首页 > 其他分享 >回溯:排列回溯和组合回溯的区别

回溯:排列回溯和组合回溯的区别

时间:2024-03-15 21:23:11浏览次数:21  
标签:排列 组合 递归 元素 选择 startIndex used 回溯

在形式上,最明显的问题就是[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

相关文章

  • 洛谷题单指南-二叉树-P1030 [NOIP2001 普及组] 求先序排列
    原题链接:https://www.luogu.com.cn/problem/P1030题意解读:已知中序、后序,求先序。解题思路:与洛谷题单指南-二叉树-P1827[USACO3.4]美国血统AmericanHeritage非常类似,不在介绍过程,直接给出代码。100分代码:#include<bits/stdc++.h>usingnamespacestd;stringin,post......
  • 40. 组合总和 IIc
    /***Returnanarrayofarraysofsize*returnSize.*Thesizesofthearraysarereturnedas*returnColumnSizesarray.*Note:Bothreturnedarrayand*columnSizesarraymustbemalloced,assumecallercallsfree().*/inttemp[100];intcmp(const......
  • 39. 组合总和c
    脑残了,参数传错了,debug了半天。/***Returnanarrayofarraysofsize*returnSize.*Thesizesofthearraysarereturnedas*returnColumnSizesarray.*Note:Bothreturnedarrayand*columnSizesarraymustbemalloced,assumecallercallsfree().*/int......
  • 17. 电话号码的字母组合c
    /***Note:Thereturnedarraymustbemalloced,assumecallercallsfree().*/charc[10][10]={"","","abc\0","def\0","ghi\0","jkl\0","mno\0","pqrs\0","tuv\0&q......
  • 77. 组合c
    /***Returnanarrayofarraysofsize*returnSize.*Thesizesofthearraysarereturnedas*returnColumnSizesarray.*Note:Bothreturnedarrayand*columnSizesarraymustbemalloced,assumecallercallsfree().*/inttemp[100];voiddfs(int**......
  • CF575H Bots 题解 组合数学
    Bots传送门SashaandIraaretwobestfriends.Buttheyaren’tjustfriends,theyaresoftwareengineersandexpertsinartificialintelligence.Theyaredevelopinganalgorithmfortwobotsplayingatwo-playergame.Thegameiscooperativeandturn......
  • LC 17.电话号码的字母组合
    17.电话号码的字母组合给定一个仅包含数字2-9的字符串,返回所有它能表示的字母组合。答案可以按任意顺序返回。给出数字到字母的映射如下(与电话按键相同)。注意1不对应任何字母。示例1:输入:digits=“23”输出:[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd......
  • 代码随想录训练营第44天 | 动态规划:完全背包理论基础、​​​​​​LeetCode 518.零钱
    目录动态规划:完全背包理论基础文章讲解:代码随想录(programmercarl.com)视频讲解:带你学透完全背包问题!_哔哩哔哩_bilibili思路​​​​​​LeetCode518.零钱兑换II文章讲解:代码随想录(programmercarl.com)视频讲解:518.零钱兑换II_哔哩哔哩_bilibili思路​​​​​​Le......
  • MATLAB用GARCH-EVT-Copula模型VaR预测分析股票投资组合
    全文链接:http://tecdat.cn/?p=30426原文出处:拓端数据部落公众号对VaR计算方法的改进,以更好的度量开放式基金的风险。本文把基金所持股票看成是一个投资组合,引入Copula来描述多只股票间的非线性相关性,构建多元GARCH-EVT-Copula模型来度量开放式基金的风险,并与其他VaR估计方法的预......
  • 组合数学相关恒(不)等式
    \(\texttt{First}\):组合数本身相关性质\[C_n^{m}=C_{n}^{n-m}\]\[C_n^m=\dfrac{n}{m}\timesC_{n-1}^{m-1}\]\[C_{n}^m=C_{n-1}^{m}+C_{n-1}^{m-1}\]杨辉三角。\[C_{n}^{m}=\dfrac{n-m+1}{m}\timesC_{n}^{m-1}\]展开即得,可以作为\(n\)确定,\(m\)不定的递推式......