Permutations

题目：

Given a list of numbers, return all possible permutations.

Example For nums = [1,2,3], the permutations are:

[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

接口：

class Solution {
public:
    /**
     * @param nums: A list of integers.
     * @return: A list of permutations.
     */
    vector<vector<int> > permute(vector<int> nums) {
        // write your code here

    }
};

分析：

这道题目和subsets并不同。首先退出递归的条件是当instance与nums长度相同。其次，每次递归都从0开始，只是要注意当出现重复数字之后做一个continue就好。

解法：

class Solution {
public:
    /**
     * @param nums: A list of integers.
     * @return: A list of permutations.
     */

    void dfs(vector<int> nums, 
                vector<int> instance, 
                vector<vector<int> >& res) {

        if (instance.size() == nums.size() ) {
            res.push_back(instance);
            return;
        }

        for (int i = 0; i < nums.size(); i++) {
            if (find(instance.begin(), instance.end(), nums[i]) != instance.end() ) {
                continue;
            }

            instance.push_back(nums[i]);
            dfs(nums, instance, res);
            instance.pop_back();
        }

    } 

    vector<vector<int> > permute(vector<int> nums) {
        // write your code here
       if (nums.size() == 0) {
           return vector<vector<int> >();
       }

       vector<vector<int> > res;
       vector<int> instance;

       dfs(nums, instance, res);

       return res;
    }
};