backtracking.md

Index

Combinations // 可以sort也可以不sort
Combination Sum //sum类问题，因为有target == sum要求，dfs之前最好sort一遍，这样更大的元素就不用考虑，方便剪枝
Permutations
Permutations II

Combination

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

For example,
If n = 4 and k = 2, a solution is:

[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

利用back tracking枚举可能情况，边界条件为path.size() == k，满足条件就把path vector放到result vector中

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> result;
        vector<int> path;
        
        if(n <= 0){
            return result;
        }
        trackback(result, path, n, k, 1);
        
        return result;
    }
    
    void trackback(vector<vector<int>>& result, vector<int> path, int n, int k, int level){
        
        if(path.size() == k){
            result.push_back(path);
            return;
        }
        
        if(path.size() > k){
            return;
        }
        
        for(int i = level; i <= n; i++){
            path.push_back(i);
            trackback(result, path, n, k, i + 1); //此处为i + 1，因为不涉及到返回处理，可以不用判定是否访问过，设置为i + 1即可
            path.pop_back();
        }
    }
};

Combination Sum

边界条件为 target == 0，每次路径更新target -= nums[i]，
Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is:
[
[7],
[2, 2, 3]
]

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> ret;
        
        if(candidates.size() == 0 || target < 0){
            return ret;
        }
        vector<int> curr;
        
        backtracking(ret, curr, candidates, target, 0);
        return ret;
    }
    
    void backtracking(vector<vector<int>>& ret, vector<int> curr, vector<int> candidates, int target, int level)
    {
        if(target == 0){
            ret.push_back(curr);
            return;
        }
        else if(target < 0){
            return;
        }
        
        for(int i = level; i < candidates.size(); ++i){
            target -= candidates[i];
            curr.push_back(candidates[i]);
            backtracking(ret, curr, candidates, target, i); //此处为i，只枚举i后面的数，防止有重复元素；
            curr.pop_back();
            target += candidates[i]; //释放targe值
        }
    }
};

Permutations

Given a collection of distinct numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

可以用同样的模版，但是permutation一定要有判定是否访问过了.

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<int> path;
        vector<vector<int>> result;
        bool visit[nums.size()] = {false};
        
        dfs(result, path, nums, visit);
        return result;
    }
    
    void dfs(vector<vector<int>>& result, vector<int> path, vector<int> nums, bool visit[])
    {
        if(path.size() == nums.size()){
            result.push_back(path);
            return;
        }
        
        for(int i = 0; i < nums.size(); i++){
            if(visit[i] == false){
                visit[i] = true;
                path.push_back(nums[i]);
                dfs(result, path, nums, visit);  //循环，但是访问过的元素不放入数组中
                visit[i] = false; // 释放判定
                path.pop_back();
            }
        }
    }
};

Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
于上一题一样，除了是否访问过的判定，还要加上是否重复的判定 visit[i - 1] == false && i != 0 && nums[i] == nums[i - 1]

class Solution {
public:
    
    vector<vector<int>> permuteUnique(vector<int>& num) {
        vector<vector<int>> result;
        if(num.size() == 0){
            return result;
        }
        vector<int> path;
        vector<bool> visited(num.size(), false);
        
        sort(num.begin(), num.end());
        dfs(result, path, num, visited);
        return result;
    }
    
    void dfs(vector<vector<int>>& result, vector<int> path, vector<int> num, vector<bool> visited)
    {
        if(path.size() == num.size()){
            result.push_back(path);
            return;
        }
        
        for(int i = 0; i < num.size(); i++){
            if(visited[i] == false){
                if(i != 0 && visited[i - 1] == false && num[i] == num[i - 1]){ //判定一定要考虑[i - 1]项，i != 0 在前
                    continue;
                }
                visited[i] = true;
                path.push_back(num[i]);
                dfs(result, path, num, visited);
                visited[i] = false;
                path.pop_back();
            }
        }
            
    }
};