写作网站有哪些,ps网站轮播图怎么做,做网站能月入10万,西安网站网站建设给定一个可包含重复数字的序列 nums #xff0c;按任意顺序 返回所有不重复的全排列
示例 1#xff1a;
输入#xff1a;nums [1,1,2]
输出#xff1a;
[[1,1,2],[1,2,1],[2,1,1]]
示例 2#xff1a;
输入#xff1a;nums [1,2,3]
输出#xff1a;[[1,2,3],[1,3,2…给定一个可包含重复数字的序列 nums 按任意顺序 返回所有不重复的全排列
示例 1
输入nums [1,1,2]
输出
[[1,1,2],[1,2,1],[2,1,1]]
示例 2
输入nums [1,2,3]
输出[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
回溯三部曲:
1).确定回溯函数参数
path来收集符合条件的结果result 保存 path,作为结果集used 排列问题需要标记已经选择的元素和用来记录同一树枝上的元素是否使用过
注意{1,2} 和 {2,1} 是不同的排序组合因为排序不同但 {1,2} 和 {2,1} 是相同的组合因为元素相同。所以处理组合问题需要 startIndex,处理排列问题就不用使用 startIndex 了
vectorvectorint result;
vectorint path;
void backtracking(vectorint nums,vectorbool used)
2).递归的终止条件
收割叶子节点
if(path.size() nums.size()) {result.push_back(path);return;
} 3).单层搜索的逻辑
used 是用来标记取过了哪些元素used 是bool型数组用来记录同一树枝上的元素是否使用过与leetCode 46.全排列的区别因为 nums 是可包含重复数字的序列used有去重作用
if(i0 nums[i]nums[i-1] used[i-1]false) continue;
if(used[i]true) continue; C代码:
class Solution {
public:vectorvectorint result;vectorint path;void backtracking(vectorint nums,vectorbool used) {if(path.size() nums.size()) {result.push_back(path);return;}for(int i0;inums.size();i) {if(i0 nums[i]nums[i-1] used[i-1]false) continue; if(used[i]true) continue;path.push_back(nums[i]);used[i]true;backtracking(nums,used);used[i]false;path.pop_back();}}vectorvectorint permuteUnique(vectorint nums) {sort(nums.begin(),nums.end());vectorbool used(nums.size(),false);backtracking(nums,used);return result;}
};
时间复杂度: O(n! * n)空间复杂度: O(n)
与前期文章的区别
1.leetCode 77.组合问题 、leetCode 131.切割问题、leetCode 78.子集问题需要用startIndex
startIndex 来控制for循环的起始位置used 是bool型数组用来记录同一树枝上的元素是否使用过 2.本题
每层都是从0开始搜索并不是startIndexused 是用来标记取过了哪些元素used 是bool型数组用来记录同一树枝上的元素是否使用过与leetCode 46.全排列的区别)
我的往期文章
leetCode 46. 全排列 回溯算法 图解 笔记-CSDN博客https://blog.csdn.net/weixin_41987016/article/details/134753366?spm1001.2014.3001.5501推荐和参考文章、视频
代码随想录 (programmercarl.com)https://www.programmercarl.com/0047.%E5%85%A8%E6%8E%92%E5%88%97II.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE回溯算法求解全排列如何去重| LeetCode47.全排列 II_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1R84y1i7Tm/?spm_id_from333.788vd_sourcea934d7fc6f47698a29dac90a922ba5a3
