记录生活中的点点滴滴

0%

回溯算法团灭子集、排列、组合问题

最近刷leetcode又碰到了排列组合相关的一道题,这次干脆把这些排列、组合、子集这些问题实现记录一下,巩固一下这个知识点!以下面三道题为例:

78.子集(中等)

46.全排列(中等)

77.组合(中等)

子集

输出子集,其实我们用数学算的话,很快,但是怎样把它转换成计算机所能解决的问题,这是关键!

我们找一下规律,以【1,2,3】这个数组为例,找它的子集,假设我们已经知道【1,2】的子集是:【】、【1】、【2】、【1,2】,OK,再加上一个元素3,其实就是在原来的子集集合的基础上,再每个加上3,两者相和,就是我们想要的答案。

所以,对于空集【】来说,子集就是空集【】;

如果空集加元素1,也就是集合【1】来说,它的子集就是原来的【】在加上它加上元素1 即【1】;

再加元素2,即集合【1,2】来说,它的子集就是原来的【】、【1】再加上【2】、【1,2】;

同理:。。。。

所以,我们只要从空集开始往后迭代,就能得到最终的答案,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
int len = nums.length;
res.add(new ArrayList<Integer>());
for(int num : nums){
int size = res.size();
for(int i=0;i<size;i++){
List<Integer> newList = new ArrayList<>(res.get(i));
newList.add(num);
res.add(newList);
}
}
return res;
}

排列

对待排列问题,回溯dfs去求解是最容易书写与理解的,回溯算法的关键是我们需要做选择、然后递归,完成之后需要撤销我们的选择,让它去下一次迭代!

对于这道题而言,做选择前首先还要去判断一下元素是否已经在我们的list中了,如果在的话,要跳过本次循环,不在的话再去做选择。当然,在回溯也就是dfs方法中,需要base case,它就是我们的list长度等于nums数组的长度, 说明我们已经全部选择了,可以把list添加到结果集中了,但是添加时注意要重新new一个list,不能把原来的list直接添加到结果集中。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> permute(int[] nums) {
List<Integer> list = new ArrayList<>();
backtrack(list,nums);
return res;
}
public void backtrack(List<Integer> list,int[] nums){
if(list.size()==nums.length){
List<Integer> newList = new ArrayList<>(list);
res.add(newList);
return;
}
for(int num : nums){
if(list.contains(num)){
continue;
}
//做选择,然后递归
list.add(num);
backtrack(list,nums);
//撤销选择
list.remove(list.size()-1);
}
}
}

组合

其实乍一看,这题和上道题差不多,我们是不是可以直接把base case中判断条件改一下,即如果list长度等于k就表明可以把list添加到结果集中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> combine(int n, int k) {
List<Integer> list = new ArrayList<>();
backtrack(list,k,n);
return res;
}
public void backtrack(List<Integer> list,int k,int n){
if(list.size()==k){
List<Integer> newList = new ArrayList<>(list);
res.add(newList);
return;
}
for(int i=1;i<=n;i++){
if(list.contains(i)){
continue;
}
//做选择,递归
list.add(i);
backtrack(list,k,n);
//撤销选择
list.remove(list.size()-1);
}
}
}

好的,我当时就是这么想的,看看运行一下会出现什么问题:

好家伙,发现了问题了吧!它会重复往前面去迭代,看来我们还需要在dfs方法中添加一个参数,它限制了迭代的开始节点,不然它又从1开始迭代了,OK,就是这么个思想,挺简单,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> combine(int n, int k) {
List<Integer> list = new ArrayList<>();
backtrack(list,k,n,1);
return res;
}
public void backtrack(List<Integer> list,int k,int n,int start){
if(list.size()==k){
List<Integer> newList = new ArrayList<>(list);
res.add(newList);
return;
}
for(int i=start;i<=n;i++){
if(list.contains(i)){
continue;
}
//做选择,递归
list.add(i);
backtrack(list,k,n,i+1);
//撤销选择
list.remove(list.size()-1);
}
}
}

我们再做一些优化,if(list.contains(i)){continue;},我们因为下一次判断就是从start即i+1开始的,所以没必要去判断了。这样时间击败率能从原来的7%提升到40+%;还有就是其实没必要递归到n,只需要递归到n-k+1即可,当然这时候需要我们把k的性质变一下,变成接下来还需要多少个数字,base case判断条件变成 k==0 即可!代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> combine(int n, int k) {
List<Integer> list = new ArrayList<>();
backtrack(list,k,n,1);
return res;
}
public void backtrack(List<Integer> list,int k,int n,int start){
if(k==0){
List<Integer> newList = new ArrayList<>(list);
res.add(newList);
return;
}
for(int i=start;i<=n-k+1;i++){
//做选择,递归
list.add(i);
backtrack(list,k-1,n,i+1);
//撤销选择
list.remove(list.size()-1);
}
}
}

这时候时间击败率能变成100%,Nice!

OK,这个专题就先这样了!希望以后遇到类似的可以一把分析透彻,然后解决!