[合集] Kata UL-222到了 - 未名空间MITBBS历史存档

f*m2010-05-08 07:05

1 楼

题目：
Given a collection of numbers that might contain duplicates, return all
possible unique permutations.
For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].
请教不用set的方法。
谢谢。

z*t2010-05-08 07:05

2 楼

【以下文字转载自 Love 讨论区】
发信人: Playstation3 (宇宙最强机种), 信区: Love
标题: 我也来说说我的故事
发信站: BBS 未名空间站 (Tue Nov 16 16:59:58 2010, 美东)
版上的打电话给10年前喜欢的女生的故事，看了很有感触，有人说是记流水帐，我觉得不是，喜欢一个人特别是还没有在一起的时
候，即使是一些很小的事，对方随意说过的话印象都非常深刻。
我大学毕业刚开始工作三个月后，在一个大型活动中认识了一个女孩，当时就喜欢上了
她，算是绝对的一见钟情吧。那个活动进行了有一个多星期，我和她同一个小组，基本
上天天都呆在一起，从早上到工作地点报道到晚上吃完晚饭各自回家。同组的人基本上
全都看出来我喜欢她了，但是她却傻傻地不知道，我也觉得时机不成熟，没敢表白。活
动结束后，我们回到了各自的单位，我也时不时地打个电话给她，也去她们单位找过她
，但是我也觉察到她对我没有意思，每次打完电话，心中都无比地失落。
一个月后，大学同学混到了深圳华侨城总办，邀请全班同学元旦去华侨城白吃白住白玩
。元旦的前一个晚上，卧谈会谈到了她，情绪不能自已，下决心第二天早上一大早就打
电话给她。第二天早上拨通她的电话后，跟她说了新年快乐，然后准备说些别的铺垫一
下就表白，不过说了几句觉得她态度很冷淡，心里的激情也就冷却了下来，意识到那句
话说了也是白说。于是又随便说了几句就挂了电话。回到宾馆后，想来想去，觉得要死
也死个明白，但是又想避免直接被拒的难堪，就写了一封表白信（那时候还不流行短信
），整整两页纸，当天寄出去了。
果不其然，从深圳回来的第二天就收到了拒信。。。后面的三个月，再也没有尝试和她
联系。三个月后，市里又组织了一次活动，我们俩人又都被调去帮忙，不过这次我看得
出，她故意在躲着我，我现在都还能清楚地记着发现这一点的那个下午那种万念惧灰的
感觉。后来的一年，在工作中偶而碰面，也就是点头示意，或者是装作什么事也没有发
生那样闲聊几句。我表面上虽然装得很平静，但是心里却像刀割一样疼。那阵子我终于
相信，这辈子是不可能了。但是，我仍然时不时去麦当劳吃晚饭，然后坐在那个靠窗的
位子，因为她下班搭乘的公车会从窗前经过，这样，如果她刚好坐在公车上靠麦当劳的
这边的话，我就能看到她一眼。。。一年后，我来到了美国。
来到美国以后，新的环境还有学习生活的压力，让我把这份感情压到了心理深处，我决
定忘记她，在身边找一个女朋友，开始一段真的感情。直到几个月后的一天，我以前的
同事忽然给我发了一份email,说她和xxx（我的一个朋友）要结婚了。这个消息如同晴
天霹雳，我心中那段似乎已经尘封的记忆在那时忽然苏醒过来，从认识她第一天起她的
所有片断忽然变得无比清晰，当时不知道出于什么心理，或者是要渲泄自己的情感，或
许是要给这份感情（或者是单恋）作个结束，我又给她写了一封长信（当时不知道她的
email)，信里说听说她要结婚的消息，是如何地失落，然后从认识她的第一天起开始回
忆，她那天穿的什么衣服，说了什么话，以及我对她的感觉。我对她所有的记忆，都被
记录在这几页纸上，当然最后还告诉她还依然喜欢她，但是（假惺惺地）祝福她幸福。
信寄出去后几天，又收到了同事的来信，信里问我这几天过得怎么样，然后告诉我上封
信里的那个新娘不是她，而是同名同姓的一个人，同事就是觉得很凑巧就故意写了上一
封信来恶作剧。我彻底地ft了，不过信已经寄出去了，我也无可奈何。又过了一个星期
，忽然收到了她的回信，首先她对我的婚礼祝福感到莫名其妙，但是同时似乎也很感动
，可能没有想到都快过去两年了我还依然对她如此地念念不忘，信里聊了聊她的近祝，
然后留了她的email和QQ。
有了email和QQ这两样法宝，剧情急转直上，我和她开始几乎天天聊天。可能因为两地
相距遥远，她对我几乎没有什么戒心，慢慢地她开始把工作上生活上感情上的烦恼都告
诉我，我就帮她出谋划策，在她不开心的时候安慰她。那时候她有很多人追，她觉得一
些人条件不错，但是怕他们花心怕受伤害，我当然不客气地搞破坏，劝她一定要小心谨
慎。这样几个月以后我发觉她开始慢慢喜欢上我了，但是我不敢轻举妄动，怕一步走错
满盘皆输。终于有一天，我们在QQ上聊天的时候，聊到了她表哥的一个朋友在追她的事
情，聊了好久，我这里都夜里4点多了，这时候她忽然问我，“你以前在信里说过你希
望以后去环游世界，而希望陪在你身边的人是我。你现在还是这样想吗？”我说当然了
，我永远都是这么想，她那里沉默了，那时候我心都要跳出来了，终于鼓起勇气问她“
你愿意吗？你愿意做我女朋友吗？”，她又沉默了很久，然后说“好！”
呵呵，大家可能没有猜到这个结局吧，对了，这个女孩就是我的太太，我们已经结婚好
几年了。从来没有写过我们之间的故事，不知道为什么今天这么有感触把它写出来。或
许是楼主的故事吧。其实都是一些小事，但是在楼主的记忆中却如此地清晰。和我来美
国后写第一封信给她的时候的感觉一模一样。我时常想，如果我的妻子不是她，多年以
后，我会不会时常想起这一段往事，想起我曾经刻骨铭心但又有缘无份的那个女孩呢？

x*c2010-05-08 07:05

3 楼

☆─────────────────────────────────────☆
shadowleaves (老少皆宜人畜无害) 于 (Fri Apr 16 00:13:55 2010, 美东) 提到:
Amazon买了sold by Amazon的最后一个，买完就缺货了:D
到手三大感受：
1、这个包不girly。产品照有些误导，颜色其实比较深。
2、设计非常好。这是全世界第一个真正意义上的严肃户外摄影两用包。铝骨架设计非
常棒，超过了我的gregory包，比talon 44还要舒服些。把内胆全拆掉，就立刻变成了
一个40升左右、仅重1.5kg的中型户外包。腰带和背带设计都很不错。
3、轻而大。非常模块化，我目前使用的配置是2.04kg。空间非常充足，轻松装下6x17
一机4镜，其实还有很大富裕空间。4x5，或者哈苏中幅之类的也很合适。135就更不用
提了。
缺点当然也有，$275....
☆─────────────────────────────────────☆
ifdef (ifdef) 于 (Fri Apr 16 00:16:22 2010, 美东) 提

w*x2010-05-08 07:05

4 楼

你看这样行不行：
void _inner_print(char strOrg[], char strCur[], int nLen)
{
assert(strOrg && strCur && nLen >= 0);
if (0 == nLen)
{
cout<return;
}
//record if a character is calculated as a header
//to eliminate duplicated characters
bool bRec[256];
memset(bRec, 0, sizeof(bRec));
for (int i = 0; i < nLen; i++)
{
if (!bRec[strCur[i]])
{
swap(strCur[0], strCur[i]);
_inner_print(strOrg, strCur+1, nLen-1);
swap(strCur[0], strCur[i]);
bRec[strCur[i]] = true;
}
}
}

h*32010-05-08 07:05

5 楼

要我做，就是用递归+一个prev变量。

f*m2010-05-08 07:05

6 楼

能仔细说说吗？

【在 h*****3 的大作中提到】

: 要我做，就是用递归+一个prev变量。

c*e2010-05-08 07:05

7 楼

print the permutation in lexi order, no dup will be printed.

h*32010-05-08 07:05

8 楼

好像carreer cup150上有这题？我写的最后一个test case没通过，我觉的好像他的
test case有问题，但我的思路应该没问题。
//这个子程序可以忽略不计
void swap (int &i,int &j){
int tmp;
tmp = i;
i = j;
j = tmp;
}
void permitUniq(vector &num,int res[],int lev,vector > &
list,int start)
{//res- buffer一个solution, lev - res 中的index， list- keep all
solutions,start- num中的起始位置
int prev;
vector tmp;
if(lev == num.size()){//找到一个solution, 存起来啊
tmp.assign(res,res+lev);
list.push_back(tmp);
return;
}

//开始做从start起的permutation
for(int i = start;iif(i == start){//第一个元素，没有prev，那保存下，res相应位填起来
，递归做从start+1起的permutation
prev = num[i];
res[lev] = num[i];
permitUniq(num,res,lev+1,list,start+1);
}
else if(prev != num[i]){ 不是第一个元素，那是否和前面的相等？
不相等，那res相应位填NUM[I]，和起始位置交换下位置，递归做从start+1起的
permutation，做完后得换回来，prev update
res[lev] = num[i];
swap(num[i],num[start]);
permitUniq(num,res,lev+1,list,start+1);
swap(num[start],num[i]);
prev = num[i];
}
//没else了，那就是相等了，ignore了
}

}
vector > permuteUnique(vector &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int *res= new int[num.size()];
vector > list;

if(num.size()<=1){
list.push_back(num);
delete []res;
return list;
}

sort(num.begin(),num.end());
permitUniq(num,res,0,list,0);

delete []res;
return list;

}

【在 f*********m 的大作中提到】

: 能仔细说说吗？

c*e2010-05-08 07:05

9 楼

print in lexi order, here is my code which passed both small and large tests:
class Solution {
public:
vector > permuteUnique(vector &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector > allPerm;
sort(num.begin(), num.end());

allPerm.push_back(num);
if(num.size() < 2)
return allPerm;

vector tmp=num;
while(true)
{
tmp= getNext(tmp);
if(tmp.size()==0)
break;
else
allPerm.push_back(tmp);
}

return allPerm;
}

void swap(vector &num, int i, int j)
{
int tmp = num[i];
num[i]=num[j];
num[j]=tmp;
}

vector getNext(vector perm)
{
int size= perm.size();
int i=size-1;
while(i>0 && perm[i-1] >= perm[i])
i--;

if(i<=0)
{
perm.clear();
return perm;
}

int j=size-1;
while(perm[j]<=perm[i-1])
j--;

swap(perm, j, i-1);
j=size-1;
while(i{swap(perm, i, j);
i++;
j--;
}

return perm;
}
};

i*e2010-05-08 07:05

10 楼

你最后一个 test case 之所以没通过是因为存在了重复。
这个组合 [9,0,0,0,1] 就出现了两次。

【在 h*****3 的大作中提到】

: 好像carreer cup150上有这题？我写的最后一个test case没通过，我觉的好像他的
: test case有问题，但我的思路应该没问题。
: //这个子程序可以忽略不计
: void swap (int &i,int &j){
: int tmp;
: tmp = i;
: i = j;
: j = tmp;
: }
: void permitUniq(vector &num,int res[],int lev,vector > &

h*32010-05-08 07:05

11 楼

嗯。交换以后还是得sort一遍。
改2个地方就可以了
1）paramter要改。num不用reference.
permitUniq(vector &num,int res[],int lev,vector > &
list,int start)
-〉
permitUniq(vector num,int res[],int lev,vector > &
list,int start)
2) 在for循环之前，sort一遍number，从start，到end。

【在 i**********e 的大作中提到】

: 你最后一个 test case 之所以没通过是因为存在了重复。
: 这个组合 [9,0,0,0,1] 就出现了两次。

f*m2010-05-08 07:05

12 楼

谢谢分享。

e*s2010-05-08 07:05

13 楼

为什么不用hastset，然后再写回去vector呢？这样是不是不符合题目要求？

d*n2010-05-08 07:05

14 楼

/*
trick is to sort 'num' first
Run Status: Accepted!
Program Runtime: 156 milli secs
Progress: 30/30 test cases passed.
*/
#include
#include
using namespace std ;
class Solution {
public:
int int_cmp(int i, int j){ return (ivector > permuteUnique(vector &num) {
sort(num.begin(), num.end() ) ;
vector > ret;
do{
ret.push_back( num );
}while(next_permutation(num.begin(), num.end())!=false);
return ret;
}
};

f*m2010-05-08 07:05

15 楼

题目：
Given a collection of numbers that might contain duplicates, return all
possible unique permutations.
For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].
请教不用set的方法。
谢谢。

w*x2010-05-08 07:05

16 楼

你看这样行不行：
void _inner_print(char strOrg[], char strCur[], int nLen)
{
assert(strOrg && strCur && nLen >= 0);
if (0 == nLen)
{
cout<return;
}
//record if a character is calculated as a header
//to eliminate duplicated characters
bool bRec[256];
memset(bRec, 0, sizeof(bRec));
for (int i = 0; i < nLen; i++)
{
if (!bRec[strCur[i]])
{
swap(strCur[0], strCur[i]);
_inner_print(strOrg, strCur+1, nLen-1);
swap(strCur[0], strCur[i]);
bRec[strCur[i]] = true;
}
}
}

h*32010-05-08 07:05

17 楼

要我做，就是用递归+一个prev变量。

f*m2010-05-08 07:05

18 楼

能仔细说说吗？

【在 h*****3 的大作中提到】

: 要我做，就是用递归+一个prev变量。

c*e2010-05-08 07:05

19 楼

print the permutation in lexi order, no dup will be printed.

h*32010-05-08 07:05

20 楼

好像carreer cup150上有这题？我写的最后一个test case没通过，我觉的好像他的
test case有问题，但我的思路应该没问题。
//这个子程序可以忽略不计
void swap (int &i,int &j){
int tmp;
tmp = i;
i = j;
j = tmp;
}
void permitUniq(vector &num,int res[],int lev,vector > &
list,int start)
{//res- buffer一个solution, lev - res 中的index， list- keep all
solutions,start- num中的起始位置
int prev;
vector tmp;
if(lev == num.size()){//找到一个solution, 存起来啊
tmp.assign(res,res+lev);
list.push_back(tmp);
return;
}

//开始做从start起的permutation
for(int i = start;iif(i == start){//第一个元素，没有prev，那保存下，res相应位填起来
，递归做从start+1起的permutation
prev = num[i];
res[lev] = num[i];
permitUniq(num,res,lev+1,list,start+1);
}
else if(prev != num[i]){ 不是第一个元素，那是否和前面的相等？
不相等，那res相应位填NUM[I]，和起始位置交换下位置，递归做从start+1起的
permutation，做完后得换回来，prev update
res[lev] = num[i];
swap(num[i],num[start]);
permitUniq(num,res,lev+1,list,start+1);
swap(num[start],num[i]);
prev = num[i];
}
//没else了，那就是相等了，ignore了
}

}
vector > permuteUnique(vector &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int *res= new int[num.size()];
vector > list;

if(num.size()<=1){
list.push_back(num);
delete []res;
return list;
}

sort(num.begin(),num.end());
permitUniq(num,res,0,list,0);

delete []res;
return list;

}

【在 f*********m 的大作中提到】

: 能仔细说说吗？

c*e2010-05-08 07:05

21 楼

print in lexi order, here is my code which passed both small and large tests:
class Solution {
public:
vector > permuteUnique(vector &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector > allPerm;
sort(num.begin(), num.end());

allPerm.push_back(num);
if(num.size() < 2)
return allPerm;

vector tmp=num;
while(true)
{
tmp= getNext(tmp);
if(tmp.size()==0)
break;
else
allPerm.push_back(tmp);
}

return allPerm;
}

void swap(vector &num, int i, int j)
{
int tmp = num[i];
num[i]=num[j];
num[j]=tmp;
}

vector getNext(vector perm)
{
int size= perm.size();
int i=size-1;
while(i>0 && perm[i-1] >= perm[i])
i--;

if(i<=0)
{
perm.clear();
return perm;
}

int j=size-1;
while(perm[j]<=perm[i-1])
j--;

swap(perm, j, i-1);
j=size-1;
while(i{swap(perm, i, j);
i++;
j--;
}

return perm;
}
};

i*e2010-05-08 07:05

22 楼

你最后一个 test case 之所以没通过是因为存在了重复。
这个组合 [9,0,0,0,1] 就出现了两次。

【在 h*****3 的大作中提到】

: 好像carreer cup150上有这题？我写的最后一个test case没通过，我觉的好像他的
: test case有问题，但我的思路应该没问题。
: //这个子程序可以忽略不计
: void swap (int &i,int &j){
: int tmp;
: tmp = i;
: i = j;
: j = tmp;
: }
: void permitUniq(vector &num,int res[],int lev,vector > &

h*32010-05-08 07:05

23 楼

嗯。交换以后还是得sort一遍。
改2个地方就可以了
1）paramter要改。num不用reference.
permitUniq(vector &num,int res[],int lev,vector > &
list,int start)
-〉
permitUniq(vector num,int res[],int lev,vector > &
list,int start)
2) 在for循环之前，sort一遍number，从start，到end。

【在 i**********e 的大作中提到】

: 你最后一个 test case 之所以没通过是因为存在了重复。
: 这个组合 [9,0,0,0,1] 就出现了两次。

f*m2010-05-08 07:05

24 楼

谢谢分享。

e*s2010-05-08 07:05

25 楼

为什么不用hastset，然后再写回去vector呢？这样是不是不符合题目要求？

d*n2010-05-08 07:05

26 楼

/*
trick is to sort 'num' first
Run Status: Accepted!
Program Runtime: 156 milli secs
Progress: 30/30 test cases passed.
*/
#include
#include
using namespace std ;
class Solution {
public:
int int_cmp(int i, int j){ return (ivector > permuteUnique(vector &num) {
sort(num.begin(), num.end() ) ;
vector > ret;
do{
ret.push_back( num );
}while(next_permutation(num.begin(), num.end())!=false);
return ret;
}
};

n*r2010-05-08 07:05

27 楼

谁能给讲解一下这位大牛的解法？ http://discuss.leetcode.com/questions/225/permutations-ii
Code:
class Solution {
public:
vector > permuteUnique(vector &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector used(num.size(), false);
vector path;
vector > ret;
sort(num.begin(), num.end());
sub(num, used, path, ret);
return ret;
}
void sub(vector &num, vector &used, vector &path, vector
> &ret) {
if (num.size() == path.size()) {
ret.push_back(path);
return;
}
for (int i = 0; i < num.size(); ++i) {
if (used[i] || (i != 0 && num[i] == num[i - 1] && used[i - 1]))
continue;
used[i] = true;
path.push_back(num[i]);
sub(num, used, path, ret);
used[i] = false;
path.pop_back();
}
}
};

【在 f*********m 的大作中提到】

: 题目：
: Given a collection of numbers that might contain duplicates, return all
: possible unique permutations.
: For example,
: [1,1,2] have the following unique permutations:
: [1,1,2], [1,2,1], and [2,1,1].
: 请教不用set的方法。
: 谢谢。

n*r2010-05-08 07:05

28 楼

谁能给讲解一下这位大牛的解法？ http://discuss.leetcode.com/questions/225/permutations-ii
Code:
class Solution {
public:
vector > permuteUnique(vector &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector used(num.size(), false);
vector path;
vector > ret;
sort(num.begin(), num.end());
sub(num, used, path, ret);
return ret;
}
void sub(vector &num, vector &used, vector &path, vector
> &ret) {
if (num.size() == path.size()) {
ret.push_back(path);
return;
}
for (int i = 0; i < num.size(); ++i) {
if (used[i] || (i != 0 && num[i] == num[i - 1] && used[i - 1]))
continue;
used[i] = true;
path.push_back(num[i]);
sub(num, used, path, ret);
used[i] = false;
path.pop_back();
}
}
};

【在 f*********m 的大作中提到】

: 题目：
: Given a collection of numbers that might contain duplicates, return all
: possible unique permutations.
: For example,
: [1,1,2] have the following unique permutations:
: [1,1,2], [1,2,1], and [2,1,1].
: 请教不用set的方法。
: 谢谢。

p*22010-05-08 07:05

29 楼

我写了一个练练
val arr=Array(1,1,2)
arr.permutations.toList.distinct.foreach(i=>println(i.mkString(",")))

n*r2010-05-08 07:05

30 楼

大牛这个太高深了。。。
能不能给分析一下上面那个算法的思路，想了2个小时没想明白，放弃了。

【在 p*****2 的大作中提到】

: 我写了一个练练
: val arr=Array(1,1,2)
: arr.permutations.toList.distinct.foreach(i=>println(i.mkString(",")))

p*22010-05-08 07:05

31 楼

看了一下。没感觉有什么太特别的。

【在 n****r 的大作中提到】

: 大牛这个太高深了。。。
: 能不能给分析一下上面那个算法的思路，想了2个小时没想明白，放弃了。

l*a2010-05-08 07:05

32 楼

大牛给菜鸟们展开讲讲吧

【在 p*****2 的大作中提到】

:
: 看了一下。没感觉有什么太特别的。

n*r2010-05-08 07:05

33 楼

能不能给总结一下就是这种题用dfs什么样的设计才能避免duplicate的解。
类似的简单一些的是8皇后的题，那个我感觉好理解一些。这个确实是有点儿理解起来
比较困难。
求大牛给点儿提示，感觉这也算是一类题目了。

【在 p*****2 的大作中提到】

:
: 看了一下。没感觉有什么太特别的。

p*22010-05-08 07:05

34 楼

这种题大牛你最擅长。你给大家讲讲吧。

【在 l*****a 的大作中提到】

: 大牛给菜鸟们展开讲讲吧

a*82010-05-08 07:05

35 楼

我的1和2区别很小啊，测试都过了。我的思路是2无非是有一些重复的，怎么去重复，
先排序，然后我手动run了几个test case,发现在某些情况下，会重复的swap,这样我从
后往前走，一旦遇到相同的数，就可以停止了，否则就是重复，有点排列组合的概念。
请各大牛验证：
比如 yyy9yyy9x 9,比如下个数是9，只需要换下x与9，进下一步，其他之前的不管了
，管了就重复了。
class Solution {
public:
void myPerm(vector &num, vector curv, int curi, vectorint> > &ret)
{
if(curi == num.size())ret.push_back(curv);
else
{
curv.push_back(num[curi]);
myPerm(num,curv,curi+1,ret);
for(int i = curv.size()-2; i >= 0; i--)
{
if(curv[i] == curv[curv.size()-1])break;//perm 2
swap(curv[i],curv[curv.size()-1]);
myPerm(num,curv,curi+1,ret);
swap(curv[curv.size()-1],curv[i]);
}
}
}

vector > permuteUnique(vector &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector > ret;
if(num.size() == 0)return ret;
vector v;
sort(num.begin(),num.end());//perm 2
myPerm(num,v,0,ret);
return ret;
}
};

s*g2010-05-08 07:05

36 楼

这个是可以实现的，每次循环前，查一下余下的是否有duplicate就行。

【在 h*****3 的大作中提到】

: 要我做，就是用递归+一个prev变量。

j*s2010-05-08 07:05

37 楼

public ArrayList> permuteUnique(int[] num) {
Arrays.sort(num);
ArrayList> output
= new ArrayList>();
ArrayList list = new ArrayList();
boolean col[] = new boolean[num.length];
permute(output,list,col,num,0);
return output;
}

public void permute(ArrayList> output,
ArrayList list,boolean col[],
int num[],int level)
{
if(level >= num.length)
{
output.add((ArrayList)list.clone());
return ;
}
int pre = num[0]-1; //保存上一次visit，
for(int i=0;i{
//guarantee we do not reuse a same element in this round.
if(col[i]==false && num[i] != pre)
{
col[i] = true;
if(list.size() < level+1)
list.add(num[i]);
else
list.set(level,num[i]);
permute(output,list,col,num,level+1);
col[i] = false;
pre = num[i];
}
}
}
之前看了peking2大牛写得一道类似的题，自己跟着用例子跑了一遍他的程序，算是半
学会这个基本思路。
用例子来说就是
假如input是11122
look at the first sub-problem: pick one as the first number and generate all
all permutation with this num as the first number.
我们第一次pick的是1，并生成了所有以1开头的permutation，第二次我们遇到的还是1
，如
果我们这次还是以这个1为开头(why? because the first number is 1, and
everything left is also the same)，那么这次我们所有这次生成的序列都会和上一
次重复.If you still not understand, run it step by step by hand for one time.

z*82010-05-08 07:05

38 楼

http://blog.csdn.net/zxzxy1988/article/details/8579357
基本思路就是用"next permutation"的概念，也就是下一个字典序的permutation，无
论有没有dup，都可以解决