广西开网站信息公司,云南省昆明市做网站的公司,服装设计官网,工程建设科学技术奖申报网站78.子集
与组合问题不同的就是要收集所有的子节点#xff0c;而不仅仅的叶子节点#xff1b;唯一一行代码的区别就是要把result的收集过程放到递归程序的最开始那里
class Solution {
public:vectorvectorint result;vectorint path;void traversa…78.子集
与组合问题不同的就是要收集所有的子节点而不仅仅的叶子节点唯一一行代码的区别就是要把result的收集过程放到递归程序的最开始那里
class Solution {
public:vectorvectorint result;vectorint path;void traversal(vectorint nums, int start_index) {result.push_back(path); // 收集子集要放在终止添加的上面否则会漏掉自己; 这句是唯一和组合题目不一样的一句放的位置不同就可以收集所有的节点if (start_index nums.size()) return;for( int i start_index; i nums.size(); i) {path.push_back(nums[i]);traversal(nums, i1);path.pop_back();}}vectorvectorint subsets(vectorint nums) {traversal(nums, 0);return result;}
};
90.子集II
这个题和上一个题区别就是要加上树层的去重,整体还是挺好做的有些细节还是不会写
class Solution {
public:vectorvectorint result;vectorint path;void traversal(vectorint nums, int start_index, vectorbool used) {result.push_back(path);if (start_index nums.size()) { return;}for( int i start_index; i nums.size(); i) {//if( nums[i] nums[i-1] used[i-1] false){这句不行i0会报奇怪的错if(i0 nums[i] nums[i-1] used[i-1] false){//return;//这句写错了这里应该是跳出这个循环而不是return;continue;}path.push_back(nums[i]);used[i] true;traversal(nums, i1, used);path.pop_back();used[i] false;}}vectorvectorint subsetsWithDup(vectorint nums) {vectorbool used(nums.size(), false); //这句自己还是写不出sort(nums.begin(),nums.end());traversal(nums, 0, used);return result;}
};
