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!

Related problems

Next Permutation II

Permutation Sequence

Next Permutation

Permutations

Implementation

Link: http://lintcode.com/en/problem/permutations-ii/

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> > ret;
        vector<int> path;
        vector<int> visit(nums.size(), 0);

        if(nums.size() == 0){
            ret.push_back(path);
            return ret;   
        }

        sort(nums.begin(), nums.end());

        helper(ret, path, visit, nums, 0);
        return ret;
    }

    void helper(vector<vector<int> > & ret, vector<int> & path, vector<int> & visit, vector<int> & nums, int step){

        if(nums.size() == step){
            ret.push_back(path);
            return;
        }

        for(int i = 0; i < nums.size(); i++){
            if(visit[i] == 0){
                visit[i] = 1;
                path.push_back(nums[i]);
                helper(ret, path, visit, nums, step + 1);
                path.pop_back();
                visit[i] = 0;
                while(i + 1 < nums.size() && nums[i + 1] == nums[i]) i++;
            }
        }
    }
};