Leecode热题100---78：子集（回溯）

本文主要是介绍Leecode热题100---78：子集（回溯），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

注：子集、组合与排列是不同性质的概念。子集、组合是无顺序的（{1, 2} 和{2, 1}是同一个集合），而排列是和元素顺序有关。
既然是无序，取过的元素不会重复取，写回溯算法的时候，for就要从startIndex开始，而不是从0开始！

nums = [1,2,3]为例把求子集抽象为树型结构：
在这里插入图片描述

回溯法三部曲：
1、递归函数参数
全局变量数组path为子集收集元素，二维数组result存放子集组合。
递归函数参数，需要startIndex。
2、递归终止条件
剩余集合为空的时候，就是叶子节点。即：startIndex大于数组的长度终止。
可不加终止条件，因为startIndex >= nums.size()，本层for循环结束
3、单层搜索逻辑
求取子集问题，不需要任何剪枝（没有重复的元素）！

回溯算法模版：

void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {处理节点;backtracking(路径，选择列表); // 递归回溯，撤销处理结果}
}

根据模版，写如下回溯算法：
C++：

#include<iostream>
#include<vector>
using namespace std;class Solution
{
private:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& nums,int startIndex){result.push_back(path);		// 收集子集if(startIndex >= nums.size()) return;	// 终止条件，可不加,startIndex >= nums.size()，本层for循环结束for (int i = startIndex;i<nums.size();i++){path.push_back(nums[i]);	// 子集收集元素backtracking(nums,i+1);		// 递归，注意从i+1开始，元素不重复取path.pop_back();			// 回溯}}
public:vector<vector<int>> subsets(vector<int>& nums){backtracking(nums,0);return result;}
};

python:

class Solution:def __init__(self):self.path = []self.paths = []def backtracking(self,nums,start_Index):# 收集子集，要先于终止判断self.paths.append(self.path[:])# 终止判断可不加if start_Index == len(nums):return# 单层递归逻辑for i in range(start_index,len(nums)):self.path.append(nums[i])	 # 子集收集元素self.backtracking(nums,i+1)	 # 递归，注意从i+1开始，元素不重复取self.path.pop()				# 回溯def subsets(self,nums):self.backtracking(nums,0)return self.paths