# Combination

1. 如果需要返回的组合长度不一样，则需要在外层调用dfs时加循环

2. 注意去重

time: O(2^n)

``````int[] nums;
List<List<Integer>> res = new ArrayList();
int n;
// C(m, n)
private void dfs(int start, int size, List<Integer> subset) {
if (size == subset.size()) {
return;
}
for (int i = start; i < n; i++) {
if (i > start && nums[i] == nums[i-1])  // remove duplicates
continue;
dfs(i+1, size, subset);
subset.remove(subset.size()-1);
}
}

public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
this.nums = nums;
n = nums.length;
for (int s = 0; s <= n; s++)
dfs(0, s, new ArrayList());
return res;
}``````

# Permutation

1. 如果有重复数字，需要先排序，且不能使用HashSet记录是否被使用过，
需要用一个boolean数组。

2. 注意去重

time: O(n!)

``````List<List<Integer>> res = new ArrayList();
int[] nums;
public List<List<Integer>> permute(int[] nums) {
if (nums.length == 0) return res;
this.nums = nums;
Arrays.sort(this.nums);  // help remove duplicates later
dfs(new ArrayList(), new HashSet());
return res;
}

private void dfs(List<Integer> cur, HashSet<Integer> used) {
if (cur.size() == nums.length) {
return;
}
for (int i = 0; i < nums.length; i++) {
if (used.contains(nums[i]))
continue;
if (i > 0 && !used[i-1] && arr[i] == arr[i-1]) // remove duplicates
continue;
dfs(cur, used);
used.remove(nums[i]);
cur.remove(cur.size()-1);
}
}``````

# Reference

Author:
Reprint policy: All articles in this blog are used except for special statements CC BY 4.0 reprint polocy. If reproduced, please indicate source csy99 !

Previous
dp

2020-07-19
Next
hands on: 13 preprocess
Data APILoad data from disk. dataset = tf.data.Dataset.from_tensor_slices((df.values, target.values)) Just use the belo
2020-07-19
TOC