经典组合问题

在Leetcode刷过回溯算法的同学应该都知道,组合问题是回溯算法中经典的一种题型

本篇博客给大家介绍的就是组合问题三兄弟:
39.数组总和
40.数组总和II
216.数组总和III

为什么我想说说这三道题呢,因为这三道题的本质就是套回溯算法的模版

属于只要弄明白了,那么组合问题就一定没问题了,甚至大部分的回溯算法问题也能够解决

回溯法（back tracking）（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回到上一步，重新选择,这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

回溯算法的关键在于找到终止条件,无论是子过程结束的终止条件,还是回退到上一步的终止条件.

例如 39数组总和 这道题中子过程的终止条件为

1
2
3
4
if(target==0){
    ans.add(new ArrayList<>(list));
    return;
}

回退到上一步的终止条件为
1
2
3
if(target-candidates[i]<0){
    return;
}

这就是解决问题的关键

回溯算法模版(伪代码版)

1
2
3
4
5
6
7
8
9
10
11
12
void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

回溯算法模版(详细版)就是39数组总和的代码

39数组总和

1.标准回溯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    List<List<Integer>> ans=new ArrayList<List<Integer>>();
    List<Integer> list=new ArrayList<Integer>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        backtrack(candidates,target,0);
        return ans;  
    }
    public void backtrack(int[] candidates,int target,int start){
        if(target==0){
            ans.add(new ArrayList<>(list));
            return;
        }
        for(int i=start;i<candidates.length;i++){
            if(target-candidates[i]<0){
                return;
            }
            list.add(candidates[i]);
            backtrack(candidates,target-candidates[i],i);
            list.remove(list.size()-1);
        }
    }
}

40数组总和II

跟39题非常像,就是要防止重复出现的子集

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
26
class Solution {
    List<List<Integer>> ans=new ArrayList<List<Integer>>();
    List<Integer> list=new ArrayList<Integer>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        combine(candidates,target,0);
        return ans;
    }
    public void combine(int[] candidates,int target,int start){
        if(target==0){
            ans.add(new ArrayList<>(list));
            return;
        }
        for(int i=start;i<candidates.length;i++){
            if(target-candidates[i]<0){
                return;
            }
            if(i>start&&candidates[i]==candidates[i-1]){//最关键的就是这个
                continue;
            }
            list.add(candidates[i]);
            combine(candidates,target-candidates[i],i+1);
            list.remove(list.size()-1);
        }
    }
}

216数组总和III

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
26
27
class Solution {
    List<List<Integer>> ans=new ArrayList<List<Integer>>();
    List<Integer> list=new ArrayList<Integer>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        if(n<=k){
            return ans;
        }
        combine(k,n,1);
        return ans;
    }
    public void combine(int k,int n,int start){
        if(k==0){
            if(n==0){
                ans.add(new ArrayList<>(list));
            }
            return;
        }
        for(int i=start;i<10;i++){
            if(n-i<0||k<=0){
                return;
            }
            list.add(i);
            combine(k-1,n-i,i+1);
            list.remove(list.size()-1);
        }   
    }
}