Given a collection of numbers, return all possible permutations. For example, [1,2,3] have the following permutations: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].
排列问题，
直观的排列问题如{1,2,3} 当第一次位的1 确定的时候后，需要从2，3 里面进行全排列，然后得到 1,2,3 和，1，3，2。
因此得到一个算法，用一个flags 来记录这个数是否已经被用过。
如果已经选到第n个字符（ level ==n) 那就把记录下的路径，加到输出结果里。
如果到level 还没有到字符串长度的时后，
遍历flags数组，找到第一个没有用过的字符，把这个字符加到中间的结果里，然后在把该字符标记为用过，
递归选level+1位置上的字符。
当递归结束的时候，把该字符标记为可用。
// //排列问题的解法，最基本的肯定是递归 // void getpermute(vector<int>& num, vector<vector<int>> &result, vector<int>& v, vector<bool>& flags, int level) { if(level == num.size())// end of { result.push_back(v); return; } else { for( int k=0; k<num.size(); k++) { if(flags[k] == true) continue; v[level]= num[k]; flags[k] = true; getpermute(num, result, v, flags, level+1); flags[k] = false; } } } vector<vector<int> > permute(vector<int> &num) { int len = num.size(); vector<bool> flags(len); vector<vector<int>> result; vector<int> v(len); int level =0; getpermute(num, result, v, flags, level); return result; }
这个题目的变种还可以变成，给定字符集比如 {1,2,3,4} 让你找出所有长度为3的排列。
这个怎么做呢，其实很简单，就在上面的中止条件上改成当flags = targetlength，就中止。
思路还是不变，搞个flags 数组，
当目标排列字符串数组位置level = targetlength的时候就可以把结果输出了。
如果当目标字符串数组位置level 还没有到targetlength时候
遍历整个flags的数组，找到第一个没有用过的数
标记这个数，
把这个数放到中间结果里
递归选level+1位置上的字符。
当递归结束的时候，把该字符标记为可用。
void getpermute(vector<int>& num, vector<vector<int>> &result, vector<int>& v, vector<bool>& flags, int level, int targetlength) { if (level == targetlength)// end of { result.push_back(v); return; } else { for (int k = 0; k<num.size(); k++) { if (flags[k] == true) continue; v[level]=num[k]; flags[k] = true; getpermute(num, result, v, flags, level + 1, targetlength); flags[k] = false; } } }
另外一种变种是目标集合里面包含重复的元素
一种简单的办法就是消耗空间的set，这样保证题目能做出来。
另外就要考虑如何保持消除重复，直觉关键还是在flags上。
BAXYZ
当处理X这个字符的时候，如果X==A而且A这字符已经处理过得情况下，原来的字符串变成了BAAYZ, 表明这个情况已经处理过了。
void getpermute(vector<int>& num, vector<vector<int>> &result, vector<int>& v, vector<bool>& flags, int level) { if(level == num.size())// end of { result.push_back(v); return; } else { for( int k=0; k<num.size(); k++) { if(flags[k] == true || k!=0 && num[k-1]== num[k]&& flags[k-1]) continue; //当前这个字符和前面的字符一样，并且前面的那个字符已经用过了， v[level]= num[k]; flags[k] = true; getpermute(num, result, v, flags, level+1); flags[k] = false; } } } vector<vector<int> > permuteUnique(vector<int> &num) { int len = num.size(); vector<bool> flags(len); vector<vector<int>> result; vector<int> v(len); int level =0; sort(num.begin(), num.end()); getpermute(num, result, v, flags, level); return result; }
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。