Permutation

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

Challenge
Do it without recursion.
Based on Next Permutation

Link

Lintcode_ladder

Method

1. Recursion
2. Iteration

Example

1. 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
        vector<vector<int>> result;
        if (nums.empty()) {
            return result;
        }
        int n = nums.size();
        vector<int> row;
        // start from all possible number
        for (int i = 0; i < n; ++i) {
            row.clear();
            row.push_back(nums[i]);
            helper(result, row, nums);
        }
        return result;
    }
private:
    void helper(vector<vector<int>>& result, vector<int>& row,
                vector<int>& nums) {
        // if reach the length
        if (row.size() == nums.size()) {
            result.push_back(row);
            return;
        }
        // permuatation contribute
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            // de-deup
            if (contains(row, nums[i])) {
                continue;
            }
            row.push_back(nums[i]);
            helper(result, row, nums);
            row.erase(row.begin() + row.size() - 1);
        }
        return;
    }
    // find the duplicate
    bool contains(vector<int>& row, int target) {
        int n = row.size();
        for (int i = 0; i < n; ++i) {
            if (row[i] == target) {
                return true;
            }
        }
        return false;
    }
};

Similar problems

x

Tags

x