前言

本周是學(xué)習(xí)java的第四周，本周最大的收獲是學(xué)習(xí)了容器框架和回溯算法

參考教程：

W3Cschool

本周學(xué)習(xí)要點(diǎn)：

1.判斷String相等時不要使用==而是用equals。

2.StringBuilder（一般使用）線程不安全，效率高，StringBuffer線程安全，效率低。區(qū)別于String是他們是可變字符序列。

3.在循環(huán)時字符串的拼接使用.append，否則會產(chǎn)生一大堆的對象占用空間。

4.日期的格式轉(zhuǎn)換：

        DateFormat df = new SimpleDateFormat("yyyy-MM-dd hh:mm:ss");
        String str = df.format(new Date());
        Calendar calendar = new GregorianCalendar;

5.泛型可以理解為數(shù)據(jù)類型的一個占位符（形式參數(shù)），在用到時再傳入實(shí)際類型

6.容器與數(shù)組的對比：數(shù)組不夠容器靈活，但數(shù)組效率比容器高。

7.indexOf和lastIndexOf分別返回元素在列表中的第一個或者倒數(shù)第一個的索引

題目

找出所有相加之和為 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]]

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

思路

因為題目限制只允許含有1-9的正整數(shù)，所以只要遍歷1-9，然后在回溯函數(shù)前加一個判斷，只要滿足條件就返回，代碼如下：

class Solution {
    List<List<Integer>> com = new ArrayList<>();
    public List<List<Integer>> combinationSum3(int n, int k) {
        traceBack(n,k,0,1,new ArrayList<>());
        return com;
    }
    public void traceBack(int n,int k,int sum,int start,List<Integer> list){
        if (sum==n&&k==0){
                com.add(new ArrayList<Integer>(list));
                return;
        }
        
        for(int i=start;i<10;i++){
            list.add(i);
            traceBack(n,k-1,sum+i,i+1,list);
            list.remove(list.size()-1);
        }
    }
}

這里遞歸的關(guān)鍵是將每一次遍歷的數(shù)都加入list內(nèi)，當(dāng)滿足條件時就返回，若不滿足則將最后一個元素移除然后進(jìn)入下一次遍歷；回溯的關(guān)鍵是要做到先進(jìn)后出，所以我移除了列表最后一個元素。
sum的作用是用來計算當(dāng)前加入list內(nèi)的元素的總值，而當(dāng)滿足條件時return退出當(dāng)次遞歸，避免掉不必要的循環(huán)，然后移除list最后一個元素然后加入下一次遍歷。
start是用來計算當(dāng)此遞歸內(nèi)的遍歷是從哪個數(shù)開始，去掉不需要的遞歸，在回溯中被稱作剪枝。