A simple recursion solution (C++)


  • 0
    C

    Notes:
    (Suppose input is 1,2,1,2)

    1. 2 lines modification to Permutation I;
    2. Build the answer bottom-up: {(1)} -> {(2, 1), (1, 2)} -> {(1, 2, 1), (2, 1, 1), (1, 1, 2)};
    3. To handle the duplication, find the last position plus 1 (k+1) of the duped value of current solution (s), and starting generating new solution (t).

    Code:

    vector<vector<int> > permuteUnique(vector<int> &num) {
        vector<vector<int> > res;
        if (!num.empty()) {
            vector<int> s(1, num[0]);
            permuteUnique_rec(s, num, res);
        }
        return res;
    }
    
    // s is current solution
    // num is the input
    // res is the results collection
    void permuteUnique_rec(vector<int> s, vector<int> &num, vector<vector<int> > &res) {
        size_t n = s.size();
        if (n == num.size()) {
            res.push_back(s);
        }
        else {
            size_t i, j;
            int k = n - 1;
            while (k >= 0 && num[n] != s[k]) k--;           // find the last equal-value element position
    
            for (i = k + 1; i <= n; i++) {
                vector<int> t(n + 1);
                for (j = 0; j < i; j++)  t[j] = s[j];       // copy the left
                t[j] = num[n];                              // copy the current value
                for (j = i; j < n; j++)  t[j + 1] = s[j];   // copy the right
                permuteUnique_rec(t, num, res);
            }
        }
    }

  • 0
    Z

    Copy your idea but make it with DP:

    class Solution
    {
    public:
        // Dynamic programming
        // Based on the idea at: https://oj.leetcode.com/discuss/16264/a-simple-recursion-solution-c
        vector<vector<int> > permuteUnique(vector<int> &num)
        {
            vector<vector<int>> result;
            int n = num.size();
            if(!n)
            {
                return result;
            }
            result.push_back(vector<int>(1, num[0]));
            for(int i = 1; i < n; i++)
            {
                int size = result.size();
                for(int j = 0; j < size; j++)
                {
                    vector<int> base = result[j];
                    base.push_back(num[i]);
                    result[j] = base;
                    int k = base.size() - 2;
                    while(k >= 0 && base[k] != num[i])
                    {
                        base[k + 1] = base[k];
                        result.push_back(base);
                        result.back()[k] = num[i];
                        k--;
                    }
                }
            }
            return result;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.