# Permutations

Oct 13, 2017

Given a collection of distinct 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],
[3,2,1]
]


vector<vector<int> > ret;
vector<vector<int>> permute(vector<int>& nums) {
//if (nums.size() == 0 || nums.size() == 1) return {nums};
permute(nums,0);
return ret;
}
void permute(vector<int> &nums,int beg) {
if (nums.size() - beg <= 1) {
ret.push_back(nums);
return ;
}
permute(nums,beg+1);
for(int i = beg+1;i<nums.size();i++) {
vector<int> vec = nums;
swap(vec[beg],vec[i]);
permute(vec,beg+1);
}
}


dicuss中的做法：

vector<vector<int> > permute(vector<int> &num) {
vector<vector<int> > result;

permuteRecursive(num, 0, result);
return result;
}

// permute num[begin..end]
// invariant: num[0..begin-1] have been fixed/permuted
void permuteRecursive(vector<int> &num, int begin, vector<vector<int> > &result)	{
if (begin >= num.size()) {
// one permutation instance
result.push_back(num);
return;
}

for (int i = begin; i < num.size(); i++) {
swap(num[begin], num[i]);
permuteRecursive(num, begin + 1, result);
// reset
swap(num[begin], num[i]);
}
}


LeetCodeLeetCode

Median Of Two Sorted Arrays

Combination-Sum