做资讯网站需要什么资质,做企业网的公司,网站域名空间购买,朔城网站制作题目#xff08;leecode T46#xff09;#xff1a;
给定一个不含重复数字的数组 nums #xff0c;返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 方法#xff1a;全排列是数学中的基础问题#xff0c;也是回溯算法能解决的经典问题。全排列因为每个元素都会…题目leecode T46
给定一个不含重复数字的数组 nums 返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 方法全排列是数学中的基础问题也是回溯算法能解决的经典问题。全排列因为每个元素都会用到所以不需要startIndex来控制递归的位置但由于每个元素只能使用一次而不重复所以需要使用used数组来表示当前元素是否被使用过了使用过的话就跳过当前递归。分析三部曲:
1传入参数与返回值传入nums数组与使用数组used
2终止条件全排列要求每个元素都用到了因此当path中收集的元素长度达到了nums.size时就可以收集结果并返回了
3单层处理逻辑单层中只需要判断一下当前的nums[i]是否是被使用过的如果是的话就直接退出当前递归否则的话就递归。同时记得在处理nums[i]元素时更新used数组的使用情况。
题解
class Solution {
private:vectorint path;vectorvectorint result;void backtracking(vectorint nums, vectorbool used){if(path.size() nums.size()){ //终止条件result.push_back(path);return;}for(int i 0; i nums.size(); i){ //因为每个元素都要用到无需startIndexif(used[i] true) continue;path.push_back(nums[i]);used[i] true; //注意及时更新used数组 backtracking(nums, used);path.pop_back();used[i] false;}}
public:vectorvectorint permute(vectorint nums) {path.clear();result.clear();vectorbool used(nums.size(), false); //used数组刚开始默认是全false的backtracking(nums, used);return result;}
};
