[Leetcode] Permutations / Permutations II

Permutations IIMar 17 '124943 / 12877

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].

生成的方法其实和permutation差不多，最大的差别就是unique

思考一下，生成时候的流程：每次从后面去一个数num[i]，替换num[cur]。

因为num内存在相同的数，也就是说，num[i] 可能和num[j]相同。

因此如果num[i]已经在cur这个位置上出现过，这num[j]可以直接跳过去。

class Solution {
public:
    vector<vector<int> > permuteUnique(vector<int> &num) {
        int len = num.size();
        vector<vector<int> > res;
        sort(num.begin(), num.end());
        gen(res, num, 0, len);
        return res;
    }
    
    bool isSwap(vector<int>& num, int s, int e) {
        int i = s;
        while (num[i] != num[e] && i < e) i++;
        if (i == e) return true;
        else return false;
    }
    void gen(vector<vector<int> > &res, vector<int>& num, int cur, int len) {
        if (cur == len) {
            res.push_back(num);
            return;
        }

        for (int i = cur; i < len; i++) {
            if (!isSwap(num, cur, i)) continue;
            swap(num[cur], num[i]);
            gen(res, num, cur+1, len);
            swap(num[cur], num[i]);
        }
    }
};

 

 

PermutationsMar 17 '125872 / 13772

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].

 

class Solution {
public:
    vector<vector<int> > permute(vector<int> &num) {
        int len = num.size();
        vector<vector<int> > res;
        gen(res, num, 0, len);
        return res;
    }
    void gen(vector<vector<int> > &res, vector<int>& num, int cur, int len) {
        if (cur == len) {
            res.push_back(num);
            return;
        }
        for (int i = cur; i < len; i++) {
            swap(num[cur], num[i]);
            gen(res, num, cur+1, len);
            swap(num[cur], num[i]);
        }
    }
};

 http://blog.csdn.net/morewindows/article/details/7370155