先说结论

• 本质
  • 多叉树的遍历,通过DFS+回溯剪枝实现
• 区别
  • 遍历程度不同，即return时机不同
  • 剪枝策略不同
• tips:
  • 无论哪种问题，都需要一个path[]来记录当前层的节点值（当前的决策）
  • 排列问题是可以往左走，子集/组合问题只能一路向右
  • 所以子集和组合问题的递归函数，需要多一个start入参来控制当前做决策的起点
  • 子集问题最简单
  • 组合问题通常需要辅助变量sum来判断组合的一些属性
  • 排列问题需要辅助变量visited[]来排除干扰选项
  • 称排序后的目标数组中最先出现的重复元素为正主，紧随其后的重复元素称为影子，影子可以被选择的情况只有一种：紧随正主其后

解题思路

1.理解题意，分清楚元素和选择的可重复性，共有2*2=4种情况

• 元素无重，不可复选
• 元素可重，不可复选
• 元素无重，可复选
• 元素可重，可复选（可复选的话没必要保证元素可重，本质上是第三种情况）

2.其次考虑处理的目标，即思考用“排列”还是“子集/组合”

• 通常排列问题是输出答案最多的，它需要收集决策树最深一层所有叶子结点上的元素
• 子集和组合问题是等价的，通常在决策树的遍历过程中就可以return

框架模板

元素无重，不可复选

• 子集/组合问题（主要是base case不同）

vector<int> nums;
int n = nums.size();
vector<vector<int>> res;
vector<int> path;
vector<bool>visited(n);

// 元素无重，不可复选，子集
void backtrace(vector<int>& nums,int start){

    // base case
    res.push_back(path);
    if(path.size() == nums.size())
        return;
    
    for(int i = start ; i < nums.size(); i++){
        path.push_back(nums[i]);
        backtrace(nums,i+1);    //注意这里是i+1，不是i，表明下层决策不可复选当前元素
        path.pop_back();
    }

}



// 元素无重，不可复选，组合
int sum = 0;
void backtrace(vector<int>& nums, int target, int start){

    // base case
    if( sum == target ){
        res.push_back(path);
        return;
    }

    if( sum > target )      // 剪枝
        return;     

    for(int i = start; i < nums.size(); i++){
        path.push_back(nums[i]);
        sum += nums[i];
        backtrace(nums,target,i+1)      // 注意这里是i+1，不是i，表明下层决策不可复选当前元素
        sum -= nums[i];
        path.pop_back();
    }
}

• 排列问题（visited[]）

vector<int> nums;
int n = nums.size();
vector<vector<int>> res;
vector<int> path;
vector<bool>visited(n);


// 元素无重，不可复选，排列
void backtrace(vector<int>& nums){

    // base case
    if( path.size() == nums.size()){
        res.push_back(path);
        return;
    }

    for(int i = 0;  i < nums.size(); i ++){

        if( visited[i] )
            continue;
        path.push_back(nums[i]);
        visited[i] = true;
        backtrace(nums);
        visited[i] = false;
        path.pop_back();

    }

}

元素可重，不可复选(本质是保证重复元素的相对顺序，使得只有正主出现的分支才可以出现影子)

• 子集/组合问题（主要base case不同）

vector<int> nums;
int n = nums.size();
vector<vector<int>> res;
vector<int> path;
vector<bool>visited(n);

// 元素可重，不可复选，子集
void backtrace(vector<int>& nums,int start){

    // base case
    if( path.size() == nums.size()){
        res.push_back(path);
        return;
    }

    for(int i = start ; i < nums.size(); i++){
        // 如果当前层已经做过这个决策
        if( i > start && nums[i] == nums[i-1])
            continue;
        
        for(int i = start ; i < nums.size(); i++){
            path.push_back(nums[i]);
            backtrace(nums,i+1);    // 注意这里是i+1,不是i，下一层不可再使用当前元素
            path.pop_back();
        }
    }

}

// 元素可重，不可复选，组合
int sum = 0;
void backtrace(vector<int>& nums,int target,int start){

    // base case
    if( sum == target ){
        res.push_back(path);
        return;
    }

    if( sum > target )      // 剪枝
        return;         

    for(int i = start ; i < nums.size(); i++){
        // 如果当前层已经做过这个决策
        if( i > start && nums[i] == nums[i-1])
            continue;
        
        for(int i = start ; i < nums.size(); i++){
            path.push_back(nums[i]);
            sum += nums[i];
            backtrace(nums,i+1);    // 注意这里是i+1,不是i，下一层不可再使用当前元素
            sum -= nums[i];
            path.pop_back();
        }
    }

}

• 排列问题(剪枝方法 "nums[i] == nums[i-1] && !visited[i-1]")

// 元素可重，不可复选,排列

vector<int> nums;
int n = nums.size();
vector<vector<int>> res;
vector<int> path;
vector<bool>visited(n);

void backtrace(vector<int>& nums){

    // base case
    if(path.size() == nums.size()){
        res.push_back(path);
        return;
    }

    for(int i = 0 ; i < nums.size(); i++){
        // 剪枝,如果之前层已经做过这个决策
        if( visited[i] )
            continue;

        // 剪枝,如果当前元素是影子且正主未出现
        if( i > 0 && nums[i] == nums[i-1] && !visited[i-1])
            continue;
        
        path.push_back(nums[i]);
        visited[i] = true;
        backtrace(nums);
        visited[i] = false;
        path.pop_back();
        
    }

}

元素无重，可复选（本质是做决策时不必再排除已选元素）

• 子集/组合问题(每次backtrace(i)，不必再backtrace(i+1))

vector<int> nums;
int n = nums.size();
vector<vector<int>> res;
vector<int> path;
vector<bool>visited(n);


// 元素无重，可复选，子集
void backtrace(vector<int>& nums,int start){

    // base case
    res.push_back(path);
    if(path.size() == nums.size())
        return;
    
    for(int i = start ; i < nums.size(); i++){
        path.push_back(nums[i]);
        backtrace(nums,i+1);
        path.pop_back();
    }

}

// 元素无重，可复选，组合
int sum = 0;
void backtrace(vector<int>& nums,int target,int start){

    // base case
    if(sum == target){
        res.push_back(path);
    }

    if( sum > target)       // 剪枝
        return;


    for(int i = start; i < nums.size(); i++){
        path.push_back(nums[i]);
        sum += nums[i];
        backtrace(nums,target,i);
        sum -= nums[i];
        path.pop_back();
    }

}

• 排列问题(去掉visited[])

vector<int> nums;
int n = nums.size();
vector<vector<int>> res;
vector<int> path;
vector<bool>visited(n);

void backtrace(vector<int>& nums){
    
    // base case
    if(path.size() == nums.size()){
        res.push_back(path);
        return;
    }

    for(int i = 0; i < nums.size(); i++){
        path.push_back(nums[i]);
        backtrace(nums);
        path.pop_back();
    }

}