递归函数基础

函数代码中调用自己时称为递归，该函数被称为递归函数。递归函数是一个很高效的 开发技巧，可以极大的简化代码提高开发效率。递归函数与循环类似，循环可以完成的 事情，递归函数都可以完成，并且对于一些复杂的问题，递归函数的实现代码更简单

#include<stdio.h>
 int compute_sum(int i){
   if(i > 3){
    return0;
    }
    return i + compute_sum(i+1);
}
int main(){
    printf("sum = %d\n,compute_sum(1)");
    return 0;
}
}

递归函数的一般形式

void func(){
    if(){
      ...
       return;  
    }//子集调用自己
    func;
}

练习，链表递归实现

#include<stdio.h>
#include<vector>
struct ListNode{//链表数据结构
    int val;
    ListNode *next;
    ListNode(int x):val(x),next(NULL){}
};

void add_to_vector(ListNode *head,std::vector<int> & vec){
    if(!head){//节点为空
      return;
    }
    vec.push_back(head->val);
    add_to_vector(head->next,vec);
}

int main(){
    ListNode a(1);
    ListNode b(2);
    ListNode c(3);
    ListNode d(4);
    ListNode e(5);
    a.next = &b;
    b.next = &c;
    c.next = &d;
    d.next = &e;
    std::vector<int> vec;
// 递归将head指针指向的节点数据val，push到vec里
    add_to_vector(&a,vec);
    for(int i = 0;i< vec.size();i++){
        printf("[%d]",vec[i]);
    }
    printf("\n");
    return 0;
}

回溯法

回溯法又称为试探法，但当探索到某一步时，发现原先选择达不到 目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法。

预备知识-循环

#include<stdio.h>
#include<vector>
int main(){
std::vector<int> nums;
nums.push_back(1);
nums.push_back(2);
nums.push_back(3);
std::vector<int> item;//item 生成各个子集的数组
std::vector<std:: vector<int> > result;//最终结果数组
for(int i= 0; i < nums.size(); i++){
    item.push_back(nums[i]);
    result.push_back(item);
}
for(int i =0; i < result.size();i++){
    for(int j = 0; j < result[i].size();j++){
        printf("[%d]",result[i][j]) 
}
    printf("\n");
}
return 0;
}

预备知识-递归

#include<stdio.h>
#include<vector>
//nums[] =[1,2,3], 将子集[1],[1,2],[1,2,3]递归的加入result;
void generate(int i , std::vector<int> &nums,std::vector<int> &item, std::vector<std::vector<int>> &result){
    if(i >= nums.size()){
        return;
    }
    item.push_back(nums[i]);
    result.push_back(item);
    generate(i+1,nums,item,result);
)
} 

求子集

已知一组数(其中无重复元素)，求这组数可以组成的所有子集。 结果中不可有无重复的子集。

例如: nums[] = [1, 2, 3]
结果为: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
LeetCode 78. Subsets

算法思路

利用回溯方法生成子集，即对于每个元素，都有试探放入或不放入集合中的 两个选择:
选择放入该元素，递归的进行后续元素的选择，完成放入该元素后续所有元素 的试探;之后将其拿出，即再进行一次选择不放入该元素，递归的进行后续元素的选择，完成不放入该元素后续所有元素的试探。 本来选择放入，再选择一次不放入的这个过程，称为回溯试探法。
例如:
元素数组: nums = [1, 2, 3, 4, 5,...] ，子集生成数组item[] = []
对于元素1，
选择放入item，item = [1]，继续递归处理后续[2,3,4,5,...]元素;item = [1,...]
选择不放入item，item = []，继续递归处理后续[2,3,4,5,...]元素;item = [...]

算法设计

代码实现

#include<vector>
class Solution{
public:
    std::vector<std::vector<int>> subsets(std::vector<int> &nums){
    std::vector<std::vector<int>> result;//存储最终结果的result；
    std::vector<int> item ;//回溯时产生各个子集的数组
    result.push_back(item);//将空集push进入result
    generate(0,nums,item,result);//计算各个子集
    return result；
private:
    void generate(int i , std::vector<int> &nums,std::vector<int> &item,std::vector<std::vector<int>> &result){
      if(i > = nums.size()){
        return; 
      }
      item.push_back(nums[i]);
      result.push_back(item);//将生成的子集添加进入result
      generate(i+1,nums,item,result);//第一次递归调用
      item.pop_back();
      generate(i+1,nums,item,result);//第二次递归调用
    }
};

方法2 位运算

若一个集合有三个元素A，B，C,则3个元素有2³= 8种，用0-7表示这些集合

A元素为100 = 4，B元素为010 = 2；C元素为001=1；图构造某一集合，及使用A,B,C对应的三个整数与该集合对应的整数做&运算，当为真时，将该元素push进集合

#include<vector>
class Solution{
public:
    std::vector<std:: vector<int>> subsets(std::vector<int> &nums){
    std:;vector<std::vector<int>> result;
    int all_set =   1<<nums.size() //2^n
    for(int i = 0;i<all_set;i++){遍历所有集合
        std:vector<int> item;
        for(int j = 0; j< nums.size();j++){
            if(i & (1 << j )){
                item.push_back();
            }//整数i 代表从  0 至 2^n-1^，这2^n^个集合
        }//(1 << j 构造nums数组的第j个元素
        result.push_back(item)
    }
    return result;
}
}

求子集2

已知一组数组（其中有重复元素），求这组数可以组成的所有子集。结果中无重复的子集；
例如: nums[] = [2, 1, 2, 2]
结果为: [[], [1], [1,2], [1,2,2], [1,2,2,2], [2], [2,2], [2,2,2]]
注意: [2,1,2]与[1,2,2]是重复的集合!
LeetCode 90. Subsets II
有两种重复原因:
1.不同位置的元素组成的集合是同一个子集，顺序相同: 例如: [2, 1, 2, 2] ，
选择第1,2,3个元素组成的子集:[2,1,2]; 选择第1,2,4个元素组成的子集:[2,1,2]。
2.不同位置的元素组成的集合是同一个子集，虽然顺序不同，但仍然
代表了同一个子集，因为集合中的元素是无序的。 例如: [2, 1, 2, 2] ，
选择第1,2,3个元素组成的子集:[2, 1, 2]; 选择第2,3,4个元素组成的子集:[1, 2, 2]。

算法设计

不同位置的元素组成的集合是同一个子集，子集的各个元素顺序相同 ，或顺序不同，解决办法

例如: [2, 1, 2, 2] :
选择第1,2,3个元素组成的子集:[2, 1, 2];
选择第1,2,4个元素组成的子集:[2, 1, 2];
选择第2,3,4个元素组成的子集:[1, 2, 2]。
解决方案: 先对原始nums数组进行排序，再使用set去重!
例如: [2, 1, 2, 2]排序后: [1, 2, 2, 2] 无论如何选择，均只出现[1, 2, 2]

#include<vector>
#include<set>
#include<algorithm>
class Solution{
 public:
    std::vector<std::vector<int>> subsetsWithDup(std :: vector<int> &nums){
        std::vector<std::vector<int>> result;
        std::vector<int> item;
        std::set<std::vector<int>> res_set;
        std::sort(nums.begin(),nums.end());
        result.push_back(item);
        generate(0,nums,result,item,res_set);
        return result;
   }
private:
    void generate(int i ,std::vector<int> &nums,std::vevtor<std::vector<int>> &result,std::vector<int> &item,std::set<std::vector<int>> &res_set){
    if(i > nums.size()){
      return;
    }
    item.push_back(nums[i]);
    if(res_set.find(item) == res_set.end()){
        result.push_back(item);
        res_set.insert(item);
    }
    generate(i+1,nums,result,item,res_set);
    item.pop_back();
    generate(i+1,nums,result,item,res_set);
}
};

组合数之和2

已知一数组（其中有重复元素），求这组数可以组成的所有子集，子集中的各个元素和整数target的子集，结果中无重复的子集。

LeetCode 40. Combination Sum II
无论是回溯法或位运算法，整体时间复杂度O(2^n)。 例如:
nums[] = [10, 1, 2, 7, 6, 1, 5]， target = 8;
[10] > target，则所有包含[10]的子集[10,...]，一定不满足目标。
[1, 2, 7] > target，则所有包含[1, 2, 7]的子集[1, 2, 7,...]，一定不满足目标。 [7, 6] > target，则所有包含[7, 6]的子集[7, 6,...]，一定不满足目标。

算法设计

在搜索回溯过程中进行剪枝操作: 递归调用时，计算已选择元素的和
sum，若sum >target，不再进行更 深的搜索，直接返回。
例如:
nums[] = [10, 1, 2, 7, 6, 1, 5] target = 8
...
过多的错误尝试，浪费了大量时间。

#include<vector>
#include<set>
#include<algorithm>
class Solution{
piblic:
    std::vector<std::vetor<int>> combinationSum2(std::vector<int> & candidates, int target){
    std::vector<std::vector<int>> result;
    std::vector<int> item;
    std::vector<std::vector<int>> res_item;
    std::sort(candidates.begin(),candidates.end());
    generate(0,candidates,result,item,res_set,0,target);
    return;
private:
    void generate(int i , std::vector<int> &nums,std::vector<std::vector<int>> &result, std::vector<std::vector<int>>&item,std::set<std::vector<int>> &res_set,int sum, int target){
    if(i > nums.size() || sum > target) {
        return;
    }
    sum +=nums[i];
    item.push_back(noms[i]);
    if(sum == target && res_set.find(item) == res_set.end()){
        result.push_back(item);
        res_set.push_back(item);
}
    generate(i+1,nums,result,item,res_set,sum,target);
    sum - = nums[i];
    item.pop_back();
    generate(i+1,nums,result,item,res_set,sum,target);
}

}
};