LeetCode 解题报告 (39,40)-- 数字集合中找特定和

发表于 标签 ， ，

这两道题目 39. Combination Sum和 40. Combination Sum II均要求从给定的一个数字集合中找出若干个数字的和等于某个给定的数。解决方法有两种，第一种是回溯法，第二种是动态规划。下面分别讲述。

39. Combination Sum

原题如下：

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T. The same repeated number may be chosen from C unlimited number of times.

Note: All numbers (including target) will be positive integers. Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak). The solution set must not contain duplicate combinations. For example, given candidate set 2,3,6,7 and target 7, A solution set is: [7] [2, 2, 3]

回溯法

回溯法的的过程如下：先对数组从小到大排序。然后从第一个数字开始往后加，每加上一个数字就保留当前的状态，再加上下一个数字的时候假如和超过了给定的数字，就回到上一状态，上一个状态就跳过这个数字继续往后加。注意当前数字可以重复使用。

实现方法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def combinationSum(self, candidates, target):
        res = []
        candidates.sort()
        self.dfs(candidates, target, 0, [], res)
        return res

    def dfs(self, nums, target, index, path, res):
        if target == 0:
            res.append(path)
            return 
        for i in xrange(index, len(nums)):
            if target-nums[i] < 0:
                return  # backtracking
            self.dfs(nums, target-nums[i], i, path+[nums[i]], res)

动态规划法

动态规划利用一个 list 存储每个数字可能的组合，dp [i] 表示和为 i 的数字的可能的组合，那么下一个 dp [i+1]=dp [i]+dp [1]=dp [i-1]+dp2...... 上面的加号表示对这两个可能的数字的组合进行组合。实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def combinationSum(self, candidates, target):
        dp = {}
        dp[0] = []
        for i in xrange(1,target+1):
            dp [i] = []
            if i in candidates:
                dp[i].append([i])
            for j in xrange(1,i/2+1):
                if len(dp[j]) ==0 or len(dp[i-j])==0:
                    continue
                for m in dp[j]:
                    for k in dp[i-j]:
                        tmp = m+k
                        tmp.sort()
                        if tmp not in dp[i]:
                            dp[i].append(tmp)
        return dp[target]

40. Combination Sum II

原题如下： >Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T. >Each number in C may only be used once in the combination.

Note: All numbers (including target) will be positive integers. Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak). The solution set must not contain duplicate combinations. For example, given candidate set 10,1,2,7,6,1,5 and target 8, A solution set is: [1, 7] [1, 2, 5] [2, 6] [1, 1, 6]

本题与前一题 Combination Sum 非常相似，只是附加了每个数字只能使用一次的要求。需要注意给出的 candidate numbers 中会有重复的数字。

解决方法与前一题 Combination Sum 也类似，只是在这个过程中元素不能被重复使用。

回溯法

实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def combinationSum2(self, candidates, target):
        candidates.sort()
        result = []
        self.dfs(candidates,target,0 ,[],result)
        return result

    def dfs(self, nums, tar, index, tmp, res):
        if tar == 0 :
            if tmp not in res:
                res.append(tmp)
        else:
            for i in range(index,len(nums)):
                if tar-nums[i]<0:
                    return
                self.dfs(nums, tar-nums[i], i+1, tmp+[nums[i]], res)

动态规划法

需要先获取原来的 candidates 中各个数字的个数，然后每次遇到和等于目标数字的 list 时都要判断这个 list 中的各个数字个数是否超过给定的 candidates 中的标准。 实现代码如下：

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
33
34
35
36
class Solution(object):
    def combinationSum2(self, candidates, target):
        can_dict = {}
        for candidate in candidates:
            if candidate not in can_dict: 
                can_dict[candidate] = 0
            can_dict[candidate] += 1

        dp = {}
        dp[0] = []
        for i in xrange(1,target+1):
            dp[i] = []
            if i in candidates:
                dp[i].append([i])
            for j in xrange(1,i/2+1):
                if len(dp[j])==0 or len(dp[i-j])==0:
                    continue
                for m in dp[j]:
                    for n in dp[i-j]:
                        tmp_dict = {}
                        flag = 0               
                        tmp = m+n
                        for t in tmp:
                            if t not in tmp_dict: 
                                tmp_dict[t] = 0
                            tmp_dict[t] += 1

                        for te in tmp_dict:
                            if tmp_dict[te] > can_dict[te]: 
                                flag = 1
                                break
                        if flag == 0:
                            tmp.sort()                         
                            if tmp not in dp[i]:
                                dp[i].append(tmp)
        return dp[target]