Permutations

Description

Given a list of numbers, return all possible permutations.

Notice

You can assume that there is no duplicate numbers in the list.

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]
]

Clarification

Do I need to implement KMP Algorithm in a real interview?

• Not necessary. When you meet this problem in a real interview, the interviewer may just want to test your basic implementation ability. But make sure your confirm with the interviewer first

Challenge

Do it without recursion.

Related problems

Print Numbers by Recursion

Permutation Sequence

Permutation II

Implementation

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

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> > ret;
        vector<int> path;
        vector<int> visit(nums.size(), 0);

        if(nums.size() == 0)
        {
            ret.push_back(path);
            return ret;
        }

        helper(ret, path, visit, nums, 0);
        return ret;
    }

    void helper(vector<vector<int> > & ret, vector<int> & path, vector<int> & visit, vector<int> & nums, int step){
        if(nums.size() == step){
            ret.push_back(path);
            return;
        }

        for(int i = 0; i < nums.size(); i++){
            if(visit[i] == 0){
                visit[i] = 1;
                path.push_back(nums[i]);
                helper(ret, path, visit, nums, step + 1);
                path.pop_back();
                visit[i] = 0;
            }
        }
    }
};