LeetCode: Permutations II

LeetCode: Permutations II 1
\(\)

Approach with Depth-first search

This challenge is similar with previous one: Permutations.

Except for one differient point: there are duplicate elements in array, but we need to return the all unique permutations.

For this purpose, we need to ignore the latter same element during backtraces. First we need to sort the array, then add a check for next valid index:

if(i >=1 && num[i] == num[i-1] && visited[i-1])
  continue;
class Solution {
public:
  void dfs(vector<vector<int> >& res, vector<int>& num, vector<int> now, vector<int>& visited, int index) {
    if(num.size() <= now.size()) {
      res.push_back(now);
      return;
    }
    for(int i=0; i<num.size(); i++) {
      if(!visited[i]) {
        if(i >=1 && num[i] == num[i-1] && !visited[i-1])
          continue;
        visited[i] = true;
        now.push_back(num[i]);
        dfs(res, num, now, visited, index+1);
        now.pop_back();
        visited[i] = false;
      }
    }
  }

  vector<vector<int> > permuteUnique(vector<int> &num) {
    vector<vector<int> > res;
    vector<int> now;
    vector<int> visited(num.size(), false);
    sort(num.begin(), num.end());
    if(num.size() == 0) return res;
    if(num.size() == 1) {
      res.push_back(num);
      return res;
    }
    dfs(res, num, now, visited, 0);
    return res;
  }
};

A trivial optimization

Similar with previous version of Permutations, use in-place approach will also make code simpler:

class Solution {
public:
  void dfs(vector<vector<int> >& res, vector<int> num, int index, int end) {
    if(index == end-1) {
      res.push_back(num);
      return;
    }
    for(int i=index; i< end; i++) {
        if(i != index && num[i] == num[index]) continue;
        swap(num[index], num[i]);
        dfs(res, num, index+1, end);
     }
  }

  vector<vector<int> > permuteUnique(vector<int> &num) {
    vector<vector<int> > res;
    sort(num.begin(), num.end());
    dfs(res, num, 0, num.size());
    return res;
  }
};

Time complexity: \(O(N!)\). 2020_02_10_leetcode-permutations-ii.org_20200210_184542.png

Last Updated on

Leave a Reply

Your email address will not be published. Required fields are marked *