全排列、子集合subset、目标和combation、树的路径和问题

主要的方法

1. 深度优先搜索，回溯算法
2. 宽度优先搜索
3. 是否有相同元素需要考虑等问题

针对所给问题，确定问题的解空间：

• 首先应明确定义问题的解空间，问题的解空间应至少包含问题的一个（最优）解。

• 确定结点的扩展搜索范围 for等一系列循环等问题

• 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。 判断减支情况

int a[n];
  try(int i)
{
   
   if(i>n)
     输出结果;
   else
  {
   
    for(j = 下界; j <= 上界; j=j+1)  
                    // 枚举i所有可能的路径
         {
   
    if(fun(j))      // 满足限界函数和约束条件
             {
   
          a[i] = j;
                         // 其他操作
            try(i+1);
                 回溯前的清理工作（如a[i]置空值等）;
                 }
            }
     }
  }

题目一

子集合，subset 不包括相同元素的情况

1. 深度递归优先搜索算法

// Recursion
class Solution {
   
public:
    vector<vector<int> > subsets(vector<int> &S) {
   
        vector<vector<int> > res;
        vector<int> out;
        sort(S.begin(), S.end());
        getSubsets(S, 0, out, res);
        return res;
    }
    void getSubsets(vector<int> &S, int pos, vector<int> &out, vector<vector<int> > &res) {
   
        res.push_back(out);
        // pos 是下界， size 是上界， 这也是
        for (int i = pos; i < S.size(); ++i) {
   
            out.push_back(S[i]);