f**********t
发帖数: 1001 | | C***y
发帖数: 2546 | 2 非递归的参考stl next_permutation
递归的也可以做，不过需要先排序，遇到前后相同的字符，特殊处理一下
【在 f**********t 的大作中提到】
: 想了半天，快疯了…… :(
| h**********8
发帖数: 267 | 3 mark
【在 C***y 的大作中提到】
: 非递归的参考stl next_permutation
: 递归的也可以做，不过需要先排序，遇到前后相同的字符，特殊处理一下
| n**z
发帖数: 155 | | f**********t
发帖数: 1001 | 5 嗯，想了一下。递归的首先要排序，如：1，1，2，2，3.
然后要考虑好两种情况：
1）相同的不swap。如2和2.
2）保证有重复的(如1和2)不会重复出现在开头。例如第一个1出现在开头了，第二个1
出现在开头的情况就略去 | n**z
发帖数: 155 | 6 用一个hashMap 来记住已经排过的组合行不。
这道题有点难Programmer Interview 上的那个递归算法我已经背的很难受了。 | i**********e
发帖数: 1145 | 7 利用 next_permutation 效率要好些。
代码请参考这里：
http://www.mitbbs.com/article0/JobHunting/31891031_0.html
递归的话，循环里跳到下一个不重复的元素。
例如：
[2 2 3]
=> [2 ...] ( [2 2 3] and [2 3 3] )
把重复的 2 跳过
=> [3 ...] ( [3 2 2] )
// precondition: A must be sorted
void printPermutations(int A[], int n, int count, bool used[], int perm[]) {
if (count == n) {
for (int i = 0; i < n; i++)
cout << A[perm[i]] << " ";
cout << endl;
return;
}
for (int i = 0; i < n; i++) {
if (used[i]) continue;
perm[count] = i;
used[i] = true;
printPermutations(A, n, count+1, used, perm);
used[i] = false;
// 跳过重复元素
int curr = A[i];
while (i+1 < n && A[i+1] == curr)
i++;
}
}
void printPermutations(int A[], int n) {
int perm[256];
bool used[256] = { false };
printPermutations(A, n, 0, used, perm);
}
同样的思路可以用于以下的问题，如果需要多练习递归题不妨试试吧：
http://www.ihas1337code.com/2010/09/print-all-combinations-of-n
Find all possible combination of numbers using a pre-defined candidate set.
Each number from the candidate set may be used only once in the combination.
For example,
Candidate Set = {10, 1, 2, 7, 6, 1, 5}
Target Number = 8
One possible output could be:
1+1+6
1+2+5
1+7
2+6
一些常见面试题的答案与总结 -
http://www.ihas1337code.com | f********3
发帖数: 210 | 8 mark
【在 i**********e 的大作中提到】
: 利用 next_permutation 效率要好些。
: 代码请参考这里：
: http://www.mitbbs.com/article0/JobHunting/31891031_0.html
: 递归的话，循环里跳到下一个不重复的元素。
: 例如：
: [2 2 3]
: => [2 ...] ( [2 2 3] and [2 3 3] )
: 把重复的 2 跳过
: => [3 ...] ( [3 2 2] )
: // precondition: A must be sorted
|
|
