Permutations II

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],
  [2,1,1]
]

 

class Solution {

public:

    void permute(vector<int> num, int st, int end,

                 vector<vector<int> >& ans) {

        if (st == end) {

            ans.push_back(num);

        } else {

            for (int i = st; i < end; i++) {

                // Continue if num[i] exists b/w indexes [st, i].

                int iter_back = i - 1;

                bool exists = false;

                while (iter_back >= st) {

                    if (num[iter_back] == num[i]) {

                        exists = true;

                        break;

                    }

                    iter_back--;

                }

                if (exists == true) {

                    continue;

                }

                iter_swap(num.begin() + st, num.begin() + i);

                permute(num, st + 1, end, ans);

                iter_swap(num.begin() + i, num.begin() + st); 

            }

        }

    }

    vector<vector<int> > permuteUnique(vector<int> &num) {

        // Start typing your C/C++ solution below

        // DO NOT write int main() function

        vector<vector<int> > ans;

        if (num.size() == 0) {

            return ans;

        }

        permute(num, 0, num.size(), ans);

        return ans;

    }

};