leetcode216. 組合總和 III

來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/combination-sum-iii

題目描述

找出所有相加之和為 n 的 k 個數(shù)的組合，且滿足下列條件：
只使用數(shù)字1到9
每個數(shù)字 最多使用一次
返回 所有可能的有效組合的列表 。該列表不能包含相同的組合兩次，組合可以以任何順序返回。

示例 1:
輸入: k = 3, n = 7
輸出: [[1,2,4]]
解釋:
1 + 2 + 4 = 7
沒有其他符合的組合了。

示例 2:
輸入: k = 3, n = 9
輸出: [[1,2,6], [1,3,5], [2,3,4]]
解釋:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
沒有其他符合的組合了。

示例 3:
輸入: k = 4, n = 1
輸出: []
解釋: 不存在有效的組合。
在[1,9]范圍內(nèi)使用4個不同的數(shù)字，我們可以得到的最小和是1+2+3+4 = 10，因?yàn)?0 > 1，沒有有效的組合。

提示:
2 <= k <= 9
1 <= n <= 60

解題思路

在回溯算法里，組合也是子集問題的拓展，是子集的一部分，子集問題可以查看leetcode78 子集
在子集中，是把所有可能性列出來。
比如【1,2,3】 n = 3,k = 2
s0 是什么都不選時的子集
s1 是只選一個元素的子集

s_2 是選兩個元素的子集
和為3 ，個數(shù)為2。我們要的就是s_2 中的 [1,2] 這個結(jié)果，因此這個問題也和子集一樣，同樣可以用回溯算法的框架去解決。只是我們加上條件，篩選出s_2中的[1,2]

回溯算法的框架：
result = []
def process(選擇列表):
if 滿足結(jié)束條件:
result.add(路徑)
return
for 選擇 in 選擇列表:
做選擇
backtrack(路徑, 選擇列表)
撤銷選擇

代碼演示

class Solution {
	//記錄答案
    List<List<Integer>> ans = new LinkedList<>();
    //記錄回溯時做的選擇
    LinkedList<Integer> record = new LinkedList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        process(k,n,1);
        return ans;
    }
/**
* k 是目標(biāo)元素的個數(shù)，我們每次選擇一個時，下次遞歸時要減1
* n 要組成的目標(biāo)和，
* index 遞歸來到的下標(biāo)
*/
    public void process(int k,int n,int index){
    	//base case n < 0 表示前面選擇的數(shù)字，不符合要求，直接返回
    	//k < 0 代表選擇的個數(shù)超出了要求，不合規(guī)，直接返回
        if(n < 0 || k < 0){
            return ;
        }
        //副歌要求的情況，直接加到答案里
        if(n == 0 && k == 0){
            ans.add(new LinkedList<>(record));
            return;
        }
		//可以做出的選擇，1 到 9 
        for(int i = index;i <= 9;i++){
        	//做選擇 
            record.addLast(i);
            process(k - 1,n - i,i + 1);
            //撤銷選擇
            record.removeLast();
        }
    }
}

回溯算法專題

leetcode78 子集

leetcode77. 組合

leetcode40. 組合總和 II

leetcode90. 子集 II文章來源地址http://www.zghlxwxcb.cn/news/detail-497429.html

到了這里，關(guān)于leetcode216. 組合總和 III(回溯算法-java)的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！