算法题 - 组合总数

Posted by 渐行渐远 on Sunday, November 28, 2021 共889字

力扣上的一道算法题,39题,内容如下

给定一个无重读的正整数数组 candidates 和一个正整数 target,找出
 candidates 中所有可能使数字和为目标 target 的唯一组合
 
输入: candidates = [2,3,6,7], target = 7
输出: [[7],[2,2,3]]

感觉这是一道动态规划的问题,因为非常像是经典的背包问题:装或者不装。但动态规划求解的都是计数类问题,这个问题要求给出组合集。 加入求解的是动态方程,我们可以假设已知函数 f(i, j) 计算数组 [0…i] 的数据范围内和为 j 的数量。因为数据可以重复使用,所以,计算的时候可以 包含当前的元素,也可以不包含当前的元素。

    包含i的情况
    f(i, j) = f(i, j-candidates[i]) + 1
    
    不包含i的情况
    f(i, j) = f(i-1, j-candidates[i]) + 1

现在要计算结果集,求解的是组合,而为排列。计算这种结果集问题都使用的是回溯思想,本质上还是需要抽象成一个树的结构。怎么能构造成树的结构呢,靠减法。 根节点一般都是空,减法之后第一层节点变成了 [7-2, 7-3, 7-6, 7-7], 这个时候树上有了 4 个。然后非常让每个节点继续和 [2, 3, 6, 7] 做减法,去 创建分支。如果节点值变成了0,就是符合条件的一个解,如果大于0,重复上述的流程。如果等于 0 或者小于 0,就不需要创建子节点了。

转念一想,这其实就是一个四叉树的构造和遍历。按照上面的流程写递归的代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
// 回溯所有遇到的情况
func find(candidates []int, target int, temp []int) {

    for i := 0; i < len(candidates); i++ {
        
        less := target - candidates[i]
        if less < 0 {
            continue
        }

        temp = append(temp, candidates[i])
        if less == 0 {
            gloablResult = append(gloablResult, append([]int{}, temp...))
        } else {
            find(candidates, target - candidates[i], temp)
        }
        
        temp = temp[:len(temp)-1]
    }
}

这样写完之后,求的其实是一个排列的结果,为什么会这样呢? 正常我们遍历的时候都是从前向后遍历的,但是上面的代码中,当我们遍历到 3 的时候,它还会去排在它前面的数据中找合适的配对数据,就是有查回去了。 这样的操作其实是需要排查掉的。

这有点类似于,动态规划中,我们将二维的动态数组调整成一维的动态数组时,结果的计算顺序可能需要导致一下,因为后面的计算依赖前面的计算,但前面的 计算结果又被修改了

知道问题的原因之后,我们加一个标志,保证搜索到一个位置之后,不再向它之前搜索过得元素去找

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
// 回溯所有遇到的情况
func find(candidates []int, target int, start int, temp []int) {

    for i := start; i < len(candidates); i++ {
        
        less := target - candidates[i]
        if less < 0 {
            continue
        }

        temp = append(temp, candidates[i])
        if less == 0 {
            gloablResult = append(gloablResult, append([]int{}, temp...))
        } else {
            find(candidates, target - candidates[i], i, temp)
        }
        
        temp = temp[:len(temp)-1]
    }
}