46. Permutations

Given a collection of distinct integers, return all possible permutations.

Example:

Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

void helper(vector<int>& nums, vector<vector<int> >& res, vector<int>& cur, vector<int>& visited, int level) {
    if (level == nums.size()) {
        res.push_back(cur);
    } else {
        for (int i = 0; i < nums.size(); ++i) {
            if (visited[i] == 1) continue;
            visited[i] = 1;
            cur.push_back(nums[i]);
            helper(nums, res, cur, visited, level + 1);
            cur.pop_back();
            visited[i] = 0;
        }
    }
}
vector<vector<int>> permute(vector<int>& nums) { // time: O(n!); space: O(n!)
    vector<vector<int> > res;
    vector<int> cur, visited(nums.size(), 0);
    helper(nums, res, cur, visited, 0);
    return res;
}

void helper(vector<int>& nums, int start, vector<vector<int> >& res) {
    if (start >= nums.size()) {
        res.push_back(nums);
    } else {
        for (int i = start; i < nums.size(); ++i) {
            swap(nums[start], nums[i]);
            helper(nums, start + 1, res);
            swap(nums[start], nums[i]);
        }
    }
}
vector<vector<int>> permute(vector<int>& nums) { // time: O(n!); space: O(n!)
    vector<vector<int> > res;
    helper(nums, 0, res);
    return res;
}

47. Permutations II