Permutations II

Description

Given a list of numbers with duplicate number in it. Find all unique permutations.

Example
For numbers [1,2,2] the unique permutations are:
[
  [1,2,2],
  [2,1,2],
  [2,2,1]
]

Challenge
Using recursion to do it is acceptable. If you can do it without recursion, that would be great!

Link

Lintcode_ladder

Method

1. Recursion
2. Iteration

Example

1. 1

class Solution {
public:
    /**
     * @param nums: A list of integers.
     * @return: A list of unique permutations.
     */
    vector<vector<int> > permuteUnique(vector<int> &nums) {
        // write your code here
        vector<vector<int>> result;
        if (nums.empty()) {
            return result;
        }
        int len = nums.size();
        // row of result
        vector<int> row; 
        // record used index
        vector<bool> used(len, false);
        // sort to make duplication consecutive 
        sort(nums.begin(), nums.end()); 
        // find all permutations
        helper(result, row, used, nums);
        return result;
    }
    private:
    void helper(vector<vector<int>>& result, vector<int>& row, 
                vector<bool>& used, vector<int>& nums) {
        // return, when row is full 
        if (row.size() >= nums.size()) {
            result.push_back(row);
            return;
        }
        int len = nums.size();
        for (int i = 0; i < len; ++i) {
            // only allow: unused or first seen/ last seen
            // continue:
            //      1 condition: i used
            //      2 condition: i-1 unused and i/i-1 duplication
            // For 2 condition:
            //  "used[i-1] == false" means: prev one unused, forward permutation/first time appearance is valid
            // test case -> [2, 2, 2]
            // row : index
            // 2 : [0]
            // 2 2 : [0] [1]
            // 2 2 2: [0] [1] [2]
            // rest: continue -> such as 2 2 : [0] [2] -> [2] == [1], [1] unused
            //  "used[i-1] == true"  means: prev one used, backward permutation/last time appearance is valid
            // test case -> [2, 2, 2]
            // row : index
            // 2 : [0]
            // 2 2 :[0] [2], continue [1] -> b/c [1] == [0] and [0] used
            // 2 : [1]
            // 2 2 : [1] [0], continue [2] -> b/c [2] == [1] and [1] used
            // 2 : [2]
            // 2 2: [2] [0], continue [1] -> b/c [1] == [0] and [0] used 
            // 2 2: [2] [1],
            // 2 2 2 : [2] [1] [0], so it is backward permutation
            if (used[i] || (i > 0 && nums[i-1] == nums[i] && used[i-1] == false)) {
                continue;
            }
            row.push_back(nums[i]);
            used[i] = true;
            helper(result, row, used, nums);
            row.erase(row.begin() + row.size() -1);
            used[i] = false;
        }
        return;
    }
};

Similar problems

x

Tags

x