title: Generate all permutation of an array without duplicate result
body: <p>This is a leetcode question <a href="https://oj.leetcode.com/problems/permutations-ii/" rel="nofollow">permutation2</a>. </p>
  
  <p>Given a array <code>num</code> (element is not unique, such as 1,1,2), return all permutations without duplicate result. For example, <code>num = {1,1,2}</code> should have permutations of <code>{1,1,2},{1,2,1},{2,1,1}</code>.</p>
  
  <p>I came up with a solution as follow. Basically, I recursively generate permutations. Assuming <code>[0, begin-1]</code> is fixed, then recursively generate permutation of <code>[begin, lastElement]</code>.</p>
  
  <pre><code>vector&lt;vector&lt;int&gt; &gt; permuteUnique(vector&lt;int&gt; &amp;num) {
      vector&lt;vector&lt;int&gt; &gt; res;
      if(num.empty())
          return res;
      helper(num, 0, res);
      return res;
  }
  //0...begin-1 is already permutated
  void helper(vector&lt;int&gt; &amp;num, int begin, vector&lt;vector&lt;int&gt; &gt; &amp;res)
  {
      if(begin == num.size())
      {
          res.push_back(num);//This is a permutation
          return;
      }
      for(int i = begin; i&lt;num.size(); ++i)
      {
          if(i!=begin&amp;&amp;num[i]==num[begin])//if equal, then [begin+1,lastElement] would have same permutation, so skip
              continue;
          swap(num[i], num[begin]);
          helper(num, begin+1, res);
          swap(num[i], num[begin]);
      }
  }
  </code></pre>
  
  <p>I was wondering if this is the right solution since leetcode oj gave me Output Limit while my xCode IDE can return the right answer for several cases. </p>
  
  <p>My main concern is does this <code>if(i!=begin&amp;&amp;num[i]==num[begin])continue;</code> can really skip the duplicate result? If not, what is the counter example? </p>
  
  <p>Thanks for sharing your thoughts!</p>