Leetcode算法刷题笔记-递归与回溯

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Leetcode算法刷题笔记-递归与回溯，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2461字，纯文字阅读大概需要4分钟。

内容图文

Leetcode 78. 子集

给你一个整数数组 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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/subsets/
方法壹：循环

#include<bits/stdc++.h>

using namespace std;

int main(){
	vector<int> nums;
	nums.push_back(1);
	nums.push_back(2);
	nums.push_back(3);
	vector<int> subset; //各个子集数组 
	vector<vector<int> > result; //最终结果数组
	for(int i=0;i<nums.size();i++){
		subset.push_back(nums[i]);
		result.push_back(subset);
	} 
	for(int i=0;i<result.size();i++){
		for(int j=0;j<result[i].size();j++){
			cout<<"["<<result[i][j]<<"]";
		}
		cout<<endl;
	}
	return 0;
}

方法贰：递归

#include<bits/stdc++.h>
using namespace std;

void generate(int i,vector<int>& nums,vector<int>& subset,vector<vector<int> >&result){
	if(i>=nums.size()){//当i下标超过nums数组的长度，递归结束 
		return;
	}
	subset.push_back(nums[i]);			
	result.push_back(subset);
	generate(i+1,nums,subset,result);				
}

int main(){
	vector<int> nums;
	nums.push_back(1);
	nums.push_back(2);
	nums.push_back(3);
	vector<int> subset; //各个子集数组 
	vector<vector<int> > result; //最终结果数组
	
	generate(0,nums,subset,result);//调用函数 
	
	for(int i=0;i<result.size();i++){
		for(int j=0;j<result[i].size();j++){
			cout<<"["<<result[i][j]<<"]";
		}
		cout<<endl;
	}
	return 0;
}

方法叁：回溯

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<vector<int> > subsets(vector<int> &nums) {
        vector<vector<int> >result;
        vector<int> subset;
        result.push_back(subset);
        generate(0,nums,subset,result);
        return result;
    }
private:
	void generate(int i,vector<int> &nums,vector<int> &subset,vector<vector<int> > &result){
		if(i>=nums.size()){//递归结束条件 
			return;
		}
		subset.push_back(nums[i]);
		result.push_back(subset);//将当前生成的子集subset添加到result 
		generate(i+1,nums,subset,result);//第一次递归调用
		subset.pop_back();
		generate(i+1,nums,subset,result);//第二次递归调用，回溯 
	}    	
};
int main(){
	vector<int> nums;
	nums.push_back(1);
	nums.push_back(2);
	nums.push_back(3);
	vector<int> subset; //各个子集数组 
	vector<vector<int> > result; //最终结果数组
	Solution solve;
	result = solve.subsets(nums);//调用函数 
	
	for(int i=0;i<result.size();i++){
		for(int j=0;j<result[i].size();j++){
			cout<<"["<<result[i][j]<<"]";
		}
		cout<<endl;
	}
	return 0;
}

诚邀各校各地有志之士加入我们大学生IT学习群交流：871352155（请各位广告大佬高抬贵手，常讨论学习无关的朋友请出门右拐∑(っ°Д°;)っ）

内容总结

以上是互联网集市为您收集整理的Leetcode算法刷题笔记-递归与回溯全部内容，希望文章能够帮你解决Leetcode算法刷题笔记-递归与回溯所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---