递归函数基础

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

#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个元素有23= 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);
}

}
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏magicsoar

Effective Modern C++翻译(2)-条款1:明白模板类型推导

第一章 类型推导 C++98有一套单一的类型推导的规则:用来推导函数模板,C++11轻微的修改了这些规则并且增加了两个,一个用于auto,一个用于decltyp...

19610
来自专栏章鱼的慢慢技术路

蓝桥杯题库基础练习:进制转换

2264
来自专栏mathor

十大经典排序算法(动图演示)

不稳定:如果a原本在b的前面,而a=b,排序之后a可能会出现在b的后面。 时间复杂度:对排序数据的总的操作次数。反映当n变化时,操作次数呈现什么规律。 ...

2.1K4
来自专栏钱塘大数据

【推荐收藏】十大经典排序算法(动图演示)

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也...

932
来自专栏顶级程序员

各大排序算法性能比较及演示实例

所谓排序,即将原来无序的一个序列重新排列成有序的序列。 排序方法中涉及到稳定性,所谓稳定性,是指待排序的序列中有两个或两个以上相同的项,在排序前和排序后看这些相...

36610
来自专栏AI派

Numpy 修炼之道 (2)—— N维数组 ndarray

ndarray中的每个元素在内存中使用相同大小的块。 ndarray中的每个元素是数据类型对象的对象(称为 dtype)。

3616
来自专栏程序员互动联盟

八大排序算法

排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。 我们这里说说...

3968
来自专栏Golang语言社区

Go语言实现冒泡和快速排序

冒泡和快速排序都属于交换类排序,所谓交换排序是指借助数据元素之间互相交换进行排序的方法。 冒泡排序法 冒泡排序法是一种最简单的交换类排序方法,它是通过相邻数据的...

3587
来自专栏JavaEdge

八大排序的Java实现概述1. 插入排序—直接插入排序(Straight Insertion Sort)2. 插入排序—希尔排序(Shell`s Sort)4. 选择排序—堆排序(Heap Sort)

3596
来自专栏Java 源码分析

排序算法

选择排序: ​ 选择排序一般来说就是,我们 始终从中右边的序列中找出那些最小的元素,放在左侧,这样我们就能保证左边始终有序。 ​ 但是这个算法的复杂...

4086

扫码关注云+社区

领取腾讯云代金券