【题目】

Given a collection of numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

【分析】

无

【代码】

/*********************************
*   日期：2015-01-16
*   作者：SJF0115
*   题目: 46.Permutations
*   网址：https://oj.leetcode.com/problems/permutations/
*   结果：AC
*   来源：LeetCode
*   博客：
**********************************/
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int> > permute(vector<int> &num) {
        vector<vector<int> > result;
        if(num.empty()){
            return result;
        }//if
        vector<int> visited;
        // 递归
        DFS(num,visited,result);
        return result;
    }
private:
    void DFS(vector<int> &num,vector<int> &visited,vector<vector<int> > &result){
        // 形成一个全排列
        if(num.size() == visited.size()){
            result.push_back(visited);
            return;
        }//if
        vector<int>::iterator isVisited;
        for(int i = 0;i < num.size();i++){
            // 判断num[i]是否已经访问过
           isVisited = find(visited.begin(),visited.end(),num[i]);
           // 如果没有访问过
           if(isVisited == visited.end()){
               visited.push_back(num[i]);
               DFS(num,visited,result);
               visited.pop_back();
           }//if
        }//for
    }
};

int main(){
    Solution solution;
    vector<int> num;
    num.push_back(1);
    num.push_back(2);
    num.push_back(3);
    num.push_back(4);
    // 重新排列
    vector<vector<int> > permutes = solution.permute(num);
    // 输出
    for(int i = 0;i < permutes.size();i++){
        cout<<"[";
        for(int j = 0;j < permutes[i].size();j++){
            cout<<permutes[i][j];
        }//for
        cout<<"]"<<endl;
    }
    return 0;
}

[LeetCode]46.Permutations