2014
11-18

# LeetCode-Permutations[暴力枚举]

### Permutations

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

next_permutation()

// LeetCode, Permutations
// 时间复杂度O(n!)，空间复杂度O(1)
class Solution {
public:
vector<vector<int> > permute(vector<int> &num) {
vector<vector<int> > result;
sort(num.begin(), num.end());

do {
result.push_back(num);
} while(next_permutation(num.begin(), num.end()));
return result;
}
};

// LeetCode, Permutations
// 重新实现 next_permutation()
// 时间复杂度O(n!)，空间复杂度O(1)
class Solution {
public:
vector<vector<int>> permute(vector<int>& num) {
sort(num.begin(), num.end());

vector<vector<int>> permutations;

do {
permutations.push_back(num);
} while (next_permutation(num.begin(), num.end())); // 见第2.1节

return permutations;
}
};

递归

// LeetCode, Permutations
// 深搜，增量构造法
// 时间复杂度O(n!)，空间复杂度O(n)
class Solution {
public:
vector<vector<int> > permute(vector<int>& num) {
sort(num.begin(), num.end());

vector<vector<int>> result;
vector<int> path;  // 中间结果

dfs(num, path, result);
return result;
}
private:
void dfs(const vector<int>& num, vector<int> &path,
vector<vector<int> > &result) {
if (path.size() == num.size()) {  // 收敛条件
result.push_back(path);
return;
}

// 扩展状态
for (auto i : num) {
// 查找 i 是否在path 中出现过
auto pos = find(path.begin(), path.end(), i);

if (pos == path.end()) {
path.push_back(i);
dfs(num, path, result);
path.pop_back();
}
}
}
};

Java代码:

public class Solution {
public static List<List<Integer>> permute(int[] num) {
List<List<Integer>> res = new ArrayList();
perm(0,num,res);
return res;
}
public static void swap(int arr[],int i,int j){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public static void perm(int start,int[] num,List<List<Integer>> res){
if(start >= num.length){
List<Integer> tmp = new ArrayList<Integer>(num.length);
return;
}
for(int i=start; i<num.length; i++){
swap(num, start, i);
perm(start+1,num,res);
swap(num, start, i);
}
}
}

Permutations II

Next Permutation

Permutation Sequence

Combinations

1. #!/usr/bin/env python
def cou(n):
arr =
i = 1
while(i<n):
arr.append(arr[i-1]+selfcount(i))
i+=1
return arr[n-1]

def selfcount(n):
count = 0
while(n):
if n%10 == 1:
count += 1
n /= 10
return count