BM56 有重复项数字的全排列

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    vector<vector<int> > permuteUnique(vector<int> &num) {
        std::sort(num.begin(),num.end());
        vector<vector<int> > res;
        int n=num.size();
        std::vector<int> path;
        std::vector<bool> visit(n,0);
        if(0!=n){
            conv(num,res,path,visit);
        }
        return res;
    }
    void conv(std::vector<int>&num,std::vector<std::vector<int>>& res,
              std::vector<int>&path,std::vector<bool>& visit){
        if(path.size()==num.size()){
            res.push_back(path);
            return;
        }
        for(int i=0;i<num.size();i++){
            if(visit[i]) continue;
            if(i&&(num[i]==num[i-1])&&!visit[i-1]){
                continue;
            }
            visit[i]=true;
            path.push_back(num[i]);
            conv(num,res,path,visit);
            visit[i]=false;
            path.pop_back();

        }
    }

};
int main(){
    std::vector<int> data={1,1,3};
    Solution so;
    vector<vector<int> > ret=so.permuteUnique(data);
    int n=ret.size();
    for(int i=0;i<n;i++){
        int l=ret[i].size();
        for(int j=0;j<l;j++){
            std::cout<<ret[i].at(j)<<" ";
        }
        std::cout<<std::endl;
    }
    return 0;
}

 这里实现的代码，基本上是从博客[1]中抄袭的。这里主要解释下下面if语句中的判断条件是怎么起到筛选的作用的（筛除重复的组合）。尤其是!visit[i-1]的条件有点难以理解。

 if(i&&(num[i]==num[i-1])&&!visit[i-1]){
        continue;
 }

 假设测试序列为data={1,1,3}，索引序号i为0,1,2。索引序号i的全排列为：

 在执行for循环的过程中，没有被if条件过滤的数值组合，被存储到res.push_back(path)。针对data[i], data[j], data[k]序列重复的场景，可以观察if条件是否滤除的规律：

重复值对应索引序号按照升序排列的，数字排列留存。否则，就会被if条件滤除，执行continue.

 由于data[0]=data[1]，索引序号(0,1,2)和索引序号(1,0,2)对应的值排列是相同的。索引序号(0,1,2)对应的排列，可以留下，而(1,0,2)对应的排列需要筛除。需要筛除的排列data[1], data[0], data[2]，序号1在前，0在后面，可以认为是乱序的。
 在for循环中，通过visit[i]标记节点num[i]是否访问。当num[i]==num[i-1]，说明数据重复，!visit[i-1]说明i-1对应的节点未被访问，假设continue语句不存在，则最终形成的序列B为:...data[i].....data[i-1]...。通过交换data[i]和data[i-1]，可以得到序列A：...data[i-1].....data[i]...。
序列A和序列B是等价的。B序列对应的重复值的索引位置，是按照升序排列的。而if中的判定条件，就可以筛除序列A。

Reference：
[1]全排列(有重复项数字和无重复数字)