网站及新媒体账号建设发布形式,海南省城乡建设厅网站,八戒网设计官网,网站制作目标及要求思路#xff1a;这是一道暴力搜索问题#xff0c;我们需要列出答案的所有可能组合。 题目给我们一个数组#xff0c;我们很容易想到的做法是将数组中的元素进行排列#xff0c;如何区分已选中和未选中的元素#xff0c;容易想到的是建立一个标记数组#xff0c;已经选中的…思路这是一道暴力搜索问题我们需要列出答案的所有可能组合。 题目给我们一个数组我们很容易想到的做法是将数组中的元素进行排列如何区分已选中和未选中的元素容易想到的是建立一个标记数组已经选中的元素标记为true这里采用了另一种做法采用first这一个常量指针将数组分割为为选中元素的数组和已选中元素的数组 然后就是排序问题在backtrack函数里有一个for循环通过指针i来遍历未选中数组中的元素得到所有可能的组合 代码
class Solution {
public:void backtrack(vectorvectorint res, vectorint output, int first, int len){if (first len)//终止条件{res.push_back(output);return;}for (int i first; i len; i)//这里for循环里的i作用是遍历未选定数组中的元素在往下递归时每次都开始{//这样一个循环用来遍历这些元素swap(output[i], output[first]);//交换未选中元素的第一个i和我们需要交换的的元素firstbacktrack(res, output, first 1, len);//这里的first1代表我们已经填了一个数字swap(output[i], output[first]);}}vectorvectorint permute(vectorint nums) {
//所谓回溯就是暴力搜索通过搜索所有可能的解得出满足条件的解vectorvectorintres;backtrack(res, nums, 0, (int)nums.size());return res;}
};
