大香蕉黄色网,www.男人天堂,操逼手机高清免费看,免费无码一级A片大黄在线观看,新版天堂资源中文网,一区二区三区无码免费,青青草天天干,国产一級A片免费看

算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選！

今天和大家聊的問題叫做 組合總和 III，我們先來看題面：

https://leetcode-cn.com/problems/combination-sum-iii/

Find all valid combinations of k numbers that sum up to n such that the following conditions are true:

Only numbers 1 through 9 are used.
Each number is used at most once.

Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.

題意

找出所有相加之和為 n 的 k 個數(shù)的組合。組合中只允許含有 1 - 9 的正整數(shù)，并且每種組合中不存在重復(fù)的數(shù)字。

說明：

所有數(shù)字都是正整數(shù)。
解集不能包含重復(fù)的組合。

示例

示例 1:

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

示例 2:

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

解題

碰到這種題直接用DFS一波帶走，結(jié)束遞歸的條件-成功:和為n且組合個數(shù)為k，失敗:和大于n或者組合個數(shù)大于k。

需要在每次找到組合后刪除最后一個添加元素，才能結(jié)束這輪遞歸；每輪在遞歸結(jié)束必須把當(dāng)前最后一個元素刪除。

因為所求為組合，且數(shù)字不能重復(fù)，所以設(shè)置變量start，從1開始往下走，每次遞歸start的值為當(dāng)前所選值+1

class Solution {
    private static List<List<Integer>> list;
    private static List<Integer> tem;
    public List<List<Integer>> combinationSum3(int k, int n) {
        list = new ArrayList<List<Integer>>();
        tem = new ArrayList<>();
        dfs(k,n,0,0,1);
        return list;
    }
 
    public void dfs(int k, int n,int sum,int cnt,int start) {
        for (int i = start; i < 10; i++) {
            if(sum+i > n || tem.size() > k) {
                return;
            }
            tem.add(i);
            if(sum+i == n && tem.size() == k) {
                List<Integer> tem0 = new ArrayList<>();
                tem0.addAll(tem);
                list.add(tem0);
                tem.remove(tem.size()-1);
                return;
            }
            dfs(k,n,sum+i,cnt+1,i+1);
            if(tem.size() > 0) {
                tem.remove(tem.size()-1);
            }
        }
    }
}