[leetcode_46]Permutations

对输入的数组进行全排列，然后输出~

各种输出超时啊~各种不明白

记得之前问lisy，他说是我输出的东西大小多于应该输出的。系统判题之后直接给输出了OLE

哎。看见这个比我看见超时心里还难受，看见超时至少哥自己还可以改呢！

后来想是不是一个数组里面有重复的数据呢？我每次插入到vector的时候查一下重复是不是好一些，发现还是OLE。好桑心。

受不了了。看看别人怎么想的。

我擦。有个这道题的名字有个II，II里面的介绍是数据可能重复，也就是说这道题的数据应该不会重复！！！

看看别人的代码，思路都一样= =

突然发现，人家的更专业。

vector.clear()

就差这句话

oh shit.

加上这句话一次AC你妹！！！

附上代码，代码较水：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


class Solution {
public:
    vector<vector<int>> ans;
    bool flag[100000];
    int sum;
    vector<vector<int>> permute(vector<int> &num) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        sum = num.size();
        ans.clear();
        for(int i = 0;i < sum;i++) {
            flag[i] = false;
        }
        for(int i = 0;i < sum;i++) {
            flag[i] = true;
            vector<int> tmp(sum);
            tmp[0] = i;
            fun(tmp,1,num);
            flag[i] = false;
        }
        return ans;
    }
    void fun(vector<int> &tmp,int k,vector<int> &num) {
        if(k >= sum) {
            vector<int> numtmp(sum);
            for(int i = 0;i < sum;i++) {
                numtmp[i] = num[tmp[i]];
            }
            ans.push_back(numtmp);
            return ;
        }
        for(int i = 0;i < sum;i++) {
            if(!flag[i]) {
                flag[i] = true;
                tmp[k] = i;
                fun(tmp,k+1,num);
                flag[i] = false;
            }
        }
    }
};