Leetcode39. 组合总和

题目描述

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

  • 所有数字（包括 target）都是正整数。
  • 解集不能包含重复的组合。

示例 1：

1
2
3
4
5
6
输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
  [7],
  [2,2,3]
]

示例 2：

1
2
3
4
5
6
7
输入：candidates = [2,3,5], target = 8,
所求解集为：
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

提示：

  • 1 <= candidates.length <= 30
  • 1 <= candidates[i] <= 200
  • candidate 中的每个元素都是独一无二的。
  • 1 <= target <= 500

解题思路

这道题也是用DFS+回溯的方式暴力求解。难点在于如何重复选取元素。

暴力解法的写法有两种不同的实现。

一种方法是index来标记现在处理元素的下标，每一个元素都有选取和不选取两种状态，分别对应两个进一步的递归。递归的出口在处理完所有的元素或者target的值变为了0。在实现重复选取元素这一点上，通过对index的赋值来实现。在选取当前index的元素后，递归处理下一个元素，如果是不重复选取元素就为index+1，如果是重复选取元素就仍然为index。由于index之前的元素已经有选取、不选取、重复选取的操作了，继续递归下去就实现了整体的重复选取元素。

另一种方法是用循环来实现选取或者不选取。思路与第一种方法是大体一致的。要注意循环的指示i初始值就不为0，而是index，这样才不会重复。这种实现方法容易实现剪枝，当target<candidates[i]直接结束循环就可以。

具体的实现细节可以参见示例代码：

示例代码

未剪枝的两个版本：

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
28
29
30
31
32
vector<vector<int>>ans;

void DFS(vector<int>& candidates,int target,vector<int>temp,int index)
{
    if(target<0||index>=candidates.size())
    {    
        return;
    } 
    if(target<candidates[index])
    {
        index=candidates.size();
    }
    if(target==0)
    {
        ans.push_back(temp);
        return;
    }

    DFS(candidates,target,temp,index+1);
    temp.push_back(candidates[index]);
    DFS(candidates,target-candidates[index],temp,index);

}

vector<vector<int>> combinationSum(vector<int>& candidates, int target)
{
    if(candidates.empty()) return {};
    sort(candidates.begin(),candidates.end());
    vector<int>temp;
    DFS(candidates,target,temp,0);
    return ans;
}
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
vector<vector<int>>ans;

void DFS(vector<int>& candidates,int target,vector<int>&temp,int index)
{
    if(target<0) return;
    if(target==0)
    {
        ans.push_back(temp);
        return;
    }
    for(int i=index;i<candidates.size();++i)
    {
        temp.push_back(candidates[i]);
        DFS(candidates,target-candidates[i],temp,i);
        temp.pop_back();
    }

}

vector<vector<int>> combinationSum(vector<int>& candidates, int target)
{
    if(candidates.empty()) return {};
    vector<int>temp;
    DFS(candidates,target,temp,0);
    return ans;
}

剪枝后的版本：

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
vector<vector<int>>ans;

void DFS(vector<int>& candidates,int target,vector<int>&temp,int index)
{
    if(target==0)
    {
        ans.push_back(temp);
        return;
    }
    for(int i=index;i<candidates.size();++i)
    {
        if(target<candidates[i]) break;
        temp.push_back(candidates[i]);
        DFS(candidates,target-candidates[i],temp,i);
        temp.pop_back();
    }

}

vector<vector<int>> combinationSum(vector<int>& candidates, int target)
{
    if(candidates.empty()) return {};
    sort(candidates.begin(),candidates.end());
    vector<int>temp;
    DFS(candidates,target,temp,0);
    return ans;
}