sundeepblue
3/16/2014 - 9:16 PM

Given a collection of numbers, return all possible permutations. For example, [1,2,3] have the following permutations: [1,2,3], [1,3,2], [2

Given a collection of numbers, return all possible permutations. For example, [1,2,3] have the following permutations: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

Permutations.cpp
content_copyfile_download
#include <iostream>
#include <vector>
#include <string>
using namespace std;

void dfs(vector<vector<int>> &res, vector<int> one, int idx, int n, vector<int> &nums) {
	if(idx == n) {
		res.push_back(one);
		return;
	}
	for(int i=idx; i<n; i++) {
		swap(nums[idx], nums[i]);

		one.push_back(nums[idx]);
		dfs(res, one, idx+1, n, nums);
		one.pop_back();

		swap(nums[idx], nums[i]);
	}
}

vector<vector<int>> get_premutation(vector<int> &nums) {
	vector<vector<int>> res;
	vector<int> one;
	dfs(res, one, 0, nums.size(), nums);
	return res;
}

int main()
{
    vector<int> nums = {1, 2, 3};
    vector<vector<int>> res = get_premutation(nums);
    for(auto v : res) {
	    for(int i : v) cout << i << " ";
	    cout << endl;
    }
    return 0;
}