算法题 - 组合总数

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]
    }
}