2024/6/3 周一，工作日的第一天。昨晚夢到被導師說去實驗室不積極哈哈哈，風扇開到二級，早上被吹醒。買的書馬上快要到了。上午剛來準備刷題，結果去搞了一下數據庫sql，做的差不多了，還差點格式轉換就差不多出回來了。現在來做題。

1、題目描述

2、邏輯分析

無重復數組，給一個目標值target，要求在數組中找出可以使數字和等于target的所有不同組合，且數組中的元素可以被重復使用。那么怎么解呢？我沒有頭緒，看看題解怎么說。官方題解給出算法是使用搜索回溯的方法，里面涉及到深度優先搜索遞歸計算。大致思路：將整個搜索過程用一個樹來表達，即如下圖呈現，每次的搜索都會延伸出兩個分叉，直到遞歸的終止條件，這樣我們就能不重復且不遺漏地找到所有可行解：

像上圖中所示：一個個數計算，這樣就不會有被遺漏的元素了。下面看具體代碼實現。

3、代碼演示

public List<List<Integer>> combinationSum(int[] candidates, int target) {// 創建一個結果列表，用于存儲所有可能的組合List<List<Integer>> res = new ArrayList<List<Integer>>();// 創建一個臨時列表，用于存儲當前正在構建的組合List<Integer> combina = new ArrayList<>();// 調用深度優先搜索方法，開始搜索所有可能的組合dfs( candidates,  target, res , combina, 0);// 返回結果列表 return res;}// 深度優先搜索方法，用于遞歸地搜索所有可能的組合public void dfs(int[] candidates, int target, List<List<Integer>> res , List<Integer> combina, int index){// 如果已經遍歷完所有的候選數字，則直接返回if(index == candidates.length){return;}// 如果當前組合的數字之和已經等于目標值target，則將當前組合添加到結果列表中，并返回 if(target == 0){res.add(new ArrayList<Integer> (combina));return;}// 不選擇當前數字，繼續搜索下一個數字dfs(candidates, target, res, combina, index + 1);// 如果目標值target減去當前數字仍然大于等于0，則可以選擇當前數字if(target - candidates[index] >= 0){// 將當前數字添加到當前組合中 combina.add(candidates[index]);// 遞歸調用dfs，目標值變為target減去當前數字 dfs(candidates,target - candidates[index], res, combina, index);// 回溯，將當前數字從組合中移除，以便嘗試其他組合combina.remove(combina.size() - 1);}}

時間復雜度：O(S)，其中 S 為所有可行解的長度之和。空間復雜度：O(target)。
邊看邊敲完這段代碼，大致意思明了，但是對一些細枝末節的地方還是稍有欠缺，先放一放，下次再來看看。搞了幾天的后端結果發現搞錯了哈哈，只能重新開始啦，悲慘滴我嗚嗚嗚。再見啦！