leetcode刷題/回溯算法 40. 組合總和 II

40. 組合總和 II

題意:

給定一個數組 candidates 和一個目标數 target ，找出 candidates 中所有可以使數字和為 target 的組合。

candidates 中的每個數字在每個組合中隻能使用一次。

注意：解集不能包含重複的組合。

示例 1:

輸入: candidates = [10,1,2,7,6,1,5], target = 8,
輸出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
           

示例 2:

輸入: candidates = [2,5,2,1,2], target = 5,
輸出:
[
[1,2,2],
[5]
]
           

解題思路:

問	答
有什麼辦法做到不重複?	兩步走,詳細見下文
遞歸終止條件	判斷路徑總和等于目标
單層邏輯	周遊從目前坐标開始,逐個開始遞歸後面的數字
參數	原來函數的參數,還需要加上一個start表示開始位置.一個sum來記錄路徑總和.
剪枝	因為先排序,所有如果路徑總和加上目前的數大于目标時,那麼後面的數就不需要周遊了.因為都會超過.

遇到這種需要不重複的,我們需要的就是在原來遞歸的基礎上做多兩步.

1. 排序數組,讓相同的數字相鄰
2. 用一個參數來表示開始位置(start),數字往後遞歸.避免重複

代碼:

class Solution {
private:
    //用來存儲結果和去重,去的是兩個相同數字在一起時的起點,也可以用flag标記是否周遊過這個數字.
    vector<vector<int>> res;
    vector<int>path;
public:
    
//遞歸回溯
//candidates,target 是原來的參數
//start表示起始位置
//sum表示路徑總和
void backstrack(vector<int>& candidates, const int& target,const int& start,int sum)
{
    //如果路徑總和等于目标就說明找到了一種可能
	if (sum == target)
	{
		res.push_back(path);
		return;
	}
	//從目前下标開始,如果路徑總和加上目前的數字大于目标總和.那麼就不需要再周遊了
	for (int i = start; i < candidates.size() && sum + candidates[start] <= target; i++)
	{
        //如果同一層不是第一個的同時遇到重複的就不需要再壓入了,這樣就可以出去相同的結果
        if(i>start&&candidates[i]==candidates[i-1])
        {
             continue;
        }
        //添加路徑節點
		path.push_back(candidates[i]);
        //計算路徑長度
		sum += candidates[i];
        //下一位開始遞歸
		backstrack(candidates, target, i + 1, sum);
        //回溯
		sum -= candidates[i];
		path.pop_back();
	}
}
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
    //先排序,讓相同的數相鄰出現
	sort(candidates.begin(),candidates.end());
    //遞歸
	backstrack(candidates, target, 0, 0);
	//傳回結果
	return vector<vector<int>>(res.begin(),res.end());
    }
};
           

總結:

記住回溯過程如果需要不重複.那麼需要再加上兩步即可.