BackTracing_Algorithm

1. 回溯算法的总体思想一般可以用树形结构来表示，是一种全局搜索算法，一般用于解决for循环暴力搜索都无法解决的问题。
（1）一般用于解决：组合问题、排列问题、棋盘问题（N皇后、数独）、切割问题、子集问题。
（2）基本框架为：
void backtracing(参数){
    if(终止条件){
        保存这个答案，存起来;
        return;
    }
    for(循环){  //横向的结点
        执行操作，处理结点。
        backtracing(参数)//进行递归;
        回溯;
    }
    return ;
}

（3）求子集问题：
LeedCode78. 子集
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集:不能包含重复的子集。你可以按任意顺序返回解集。

示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：
输入：nums = [0]
输出：[[],[0]]

提示：
1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素 互不相同

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        //一共2^n个子集;
        vector<vector<int>> result;
        vector<int>temp;
        result.push_back(temp);
        //本题跟全排列有啥不同，全排列是数据不同的排列次序。但是本题目是子集。
        backtracing(result,nums,temp,0);
        return result;
    }

    void backtracing(vector<vector<int>>& result,vector<int> nums,vector<int> temp,int index){
        //if(index>=nums.size()) return ;
        for(int i=index;i<nums.size();i++){
            temp.push_back(nums[i]);
            result.push_back(temp);
            if(i+1<nums.size())
                backtracing(result,nums,temp,i+1);
            temp.pop_back();
        }
        return ;
    }
};