Day 54

第78题:

给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。(来自LeetCode)

说明:解集不能包含重复的子集。

1、利用回溯算法,将所有的情况都列举出来,得出结果;

  例如数组内由三个数(1、2、3),先遍历数组将1加入子集集合item,如果item此时是一个子集,将item加入结果集res;

  然后接着递归将数组内2加入子集集合item,再次递归将3加入子集集合item,其中只要item是一个子集就将七加入res;

  递归到达最后一个数字时,进行回溯,来形成其他item,加入res,最终得出结果。

  

第491题:

给定一个整型数组, 你的任务是找到所有该数组的递增子序列,递增子序列的长度至少是2。(来自LeetCode)

 1、和生成子集一样,生成子集里面没有要求子序列是升序的,这里加上判定条件升序,且将重复的子序列不加入结果集中即可(其中直接利用set集合来存储子序列可以避免重复的子序列)。

  

2、也可以不使用set集合来排除重复的子序列,直接利用set集合来保存回溯时临时集合templist退出来的那个值;

  当下一个值在set集合中存在时,说明这个元素加进子序列后其后面生成的子序列都已经在之前遍历过了,所以这里可以直接跳出此次循环,其他步骤不变。

  

第77题:

给定两个整数 n 和 k,返回 1 ... 中所有可能的 k 个数的组合。(来自LeetCode)

1、也遍历所有组合,将符合条件的加入结果集中

  

原文地址:https://www.cnblogs.com/liang-yi-/p/13574884.html