Permutations

Given a collection of numbers, return all possible permutations.

http://www.lintcode.com/en/problem/permutations/

Discussion

就是普通的排列，假定是没有重复数字的。backtracking的典型应用，在每一维上枚举candidate number的时候，该number不能被枚举过，这是跟普通backtracking不同的地方。

要会画示例图。

再说一遍：对每一个维度，枚举每一个candidate！

O(n!) run time, O(n) stack space.

Solution

 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
        int n = nums.size();
        vector<vector<int> > result;
        if(n ==0) return result;
        vector<int> solution(n, 0);
        vector<bool> used(n, false);
        backtracing(nums, 0, result, solution, used);
        return result;
    }
private:
    void backtracing(vector<int> nums, int dim, vector<vector<int> > &records,
            vector<int> &solution, vector<bool> &used) {
        int n = nums.size();
        if(dim == n) {//终止条件
            records.push_back(solution);
            return;
        }
        for(int i=0; i<n; i++) {//在给定维度dim上枚举每一个candidate，并继续下一维度
            if(used[i] == false) {//枚举的条件式该candidate从来没有被枚举过
                used[i] = true;//告诉下一维度，该candidate已经放到维度dim上了
                solution[dim] = nums[i];
                backtracing(nums, dim+1, records, solution, used);
                used[i] = false;//下次该candidate i+1放到维度dim上了，candidate i在别的维度上又可用了。这一步非常重要。
            }
        }
    }
};

如果要求非递归实现，就要调用STL next_permutation()或者自己实现该概述。具体实现和分析见Next Permutation问题。

Solution 2

用DFS实现更容易理解。关于DFS，看这个视频。

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
        vector<vector<int> > result;
        int n = nums.size();
        if(n==0) return result;
        vector<bool> status (n, false);
        vector<int> solution;
        dfs(nums, result, solution);
        return result;
    }
private:
    void dfs(vector<int> nums, vector<vector<int> > &records,
        vector<int> &solution) {
            int n = nums.size();
            if(solution.size() ==n) {
                records.push_back(solution);
                return;//这里返回，会加快速度
            }
            for(int i=0; i<n; i++) {
               auto it = find(solution.begin(), solution.end(), nums[i]);
               if(it == solution.end()) {
                   solution.push_back(nums[i]);
                   dfs(nums, records, solution);
                   solution.pop_back();
               }
            }
        }
};

Solution 3

基于交换，O(1) space.
给定i，跟之后的每一个number要么交换，要么不交换

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> result;
        helper(nums, 0, result);
        return result;
    }
private:
    void helper(vector<int>& nums, int pos, vector<vector<int>> &records) {
        if(pos == nums.size()) {
            records.emplace_back(nums);
            return;
        }
        for(int i = pos; i<nums.size(); i++) {
            swap(nums[i], nums[pos]);
            helper(nums, pos+1, records);//这里不是i+1,跟subset不一样
            swap(nums[i], nums[pos]);
        }
    }
};