216. 组合总和 III

2023-05-28,,

216. 组合总和 III

题意

找出所有相加之和为 nk 个数的组合组合中只允许含有 1 - 9 的正整数,并且每种组合中不存在重复的数字。

说明:

所有数字都是正整数。

解集不能包含重复的组合。

示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]

示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

解题思路

由于最终的结果要求是有序的,因此需要先将数组进行排序;

    回溯:维持一个路径组合,并且不断的将target减去数组中的值,直到target值为0,则把路径组合加入到最终的结果中;

    记忆化搜索:通过字典记录下每个和对应的组合,在target在不断减去数组中的值的时候,如果这个和已经出现过,那么直接返回该和对应的组合,由于新的组合是在前面的组合的基础上进行操作的,所以没有办法对前面的组合进行剪枝;

    动态规划:应该也是和2类似的思想;

实现

之前以为回溯都需要有值返回

216. 组合总和 III的相关教程结束。

《216. 组合总和 III.doc》

下载本文的Word格式文档,以方便收藏与打印。