BackTrack

code c++ algo

學習算法

Backtrack

回朔算法框架

先宣告存放符合題目要求的值和存放結果

vector<vector<int>> result;
vector<int> path;

當滿足條件將path存入result並且return

if(path.size() == 2){
    result.push_back(path)
    }

回朔有個原則是要回歸初始狀態

sum += i;
path.push_back(sum);
backtrack(sum,i);
sum -= i;
path.pop_back();

完整模板

void backtracking(参數) {
    if (終止條件) {
        存放结果;
        return;
    }
 
    for (選擇：本層集合元素(通常是遍歷目的數組或數字) ) {
        處理節點;
        backtracking(路徑，選擇列表); // 選擇列表通常為選擇的順序遞增
        回歸原本狀態;
    }
}

例題

leetcode77

class Solution {
public:
        vector<vector<int>> result;
        vector<int> path;
    void backtrack(int n,int k,int start){
        if(path.size() == k) {
            result.push_back(path);
            return;
        }
        for(int i=start;i<=n;i++){
            path.push_back(i);
            backtrack(n,k,i+1);
            path.pop_back();
        }
    }
    vector<vector<int>> combine(int n, int k) {
        backtrack(n,k,1);
        return result;
    }
};

leetcode216

class Solution {
public:
      vector<vector<int>> result;
        vector<int> path;
    void backtrack(int target,int k,int sum,int start){
        if(path.size() == k){
            if(sum == target){
                result.push_back(path);
                return ;
            }
        }
        for(int i=start;i<=9;i++){
            sum += i;
            path.push_back(i);
            backtrack(target,k,sum,i+1);
            sum -= i;
            path.pop_back();
        }
 
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        backtrack(n,k,0,1);
        return result;
    }
};