Backtracking 不变的经典啊。
唯一注意的地方是,start == nums.length 的时候其实也是要添加结果的,不然会错。写回溯的时候,base case 要想清楚。
Copy public class Solution {
public List < List < Integer >> subsets ( int [] nums) {
List < List < Integer >> rst = new ArrayList <>();
dfs(rst , new ArrayList <>() , nums , 0 ) ;
return rst;
}
private void dfs ( List < List < Integer >> rst , List < Integer > list , int [] nums , int start){
//if(start > nums.length) return;
rst . add ( new ArrayList < Integer >(list));
for ( int i = start; i < nums . length ; i ++ ){
list . add (nums[i]);
dfs(rst , list , nums , i + 1 ) ;
list . remove ( list . size () - 1 );
}
}
}
有重复元素也不难,先 sort,然后每一步上注意同样的元素别重复加一遍就好了。
Copy public class Solution {
public List < List < Integer >> subsetsWithDup ( int [] nums) {
List < List < Integer >> rst = new ArrayList <>();
Arrays . sort (nums);
dfs(rst , new ArrayList <>() , nums , 0 ) ;
return rst;
}
private void dfs ( List < List < Integer >> rst , List < Integer > list , int [] nums , int start){
rst . add ( new ArrayList < Integer >(list));
for ( int i = start; i < nums . length ; i ++ ){
list . add (nums[i]);
dfs(rst , list , nums , i + 1 ) ;
list . remove ( list . size () - 1 );
while (i + 1 < nums . length && nums[i] == nums[i + 1 ]) i ++ ;
}
}
}
这类题的搜索树都是极度向左倾斜的结构,节点数为 2^n;
Copy public class Solution {
public List < List < Integer >> combine ( int n , int k) {
List < List < Integer >> rst = new ArrayList <>();
dfs(rst , new ArrayList < Integer >() , n , k , 1 ) ;
return rst;
}
private void dfs ( List < List < Integer >> rst , List < Integer > list , int n , int k , int cur){
if (k == 0 ){
rst . add ( new ArrayList <>(list));
return ;
}
for ( int i = cur; i <= n; i ++ ){
list . add (i);
dfs(rst , list , n , k - 1 , i + 1 ) ;
list . remove ( list . size () - 1 );
}
}
}
为什么觉得我好像在这 gitbook 里写过这题。。
元素可以重复选用,传进去的 index 可以以 i 为准。
所有元素为正整数非常重要,要么这题可能有无数个解。
Copy public class Solution {
public List < List < Integer >> combinationSum ( int [] candidates , int target) {
List < List < Integer >> rst = new ArrayList <>();
dfs(rst , new ArrayList <>() , candidates , target , 0 , 0 ) ;
return rst;
}
private void dfs ( List < List < Integer >> rst , List < Integer > list , int [] nums , int target , int sum , int start){
if (sum > target) return ;
if (sum == target){
rst . add ( new ArrayList < Integer >(list));
return ;
}
for ( int i = start; i < nums . length ; i ++ ){
list . add (nums[i]);
dfs(rst , list , nums , target , sum + nums[i] , i) ;
list . remove ( list . size () - 1 );
}
}
}
没重复元素,想避免重复解,用 index 单调向前;
有重复元素,想避免重复解,index 之外每轮 dfs 末尾直接把指针移到下一个新元素上,一个元素在一轮 for loop 里只加一次。
Copy public class Solution {
public List < List < Integer >> combinationSum2 ( int [] candidates , int target) {
List < List < Integer >> rst = new ArrayList <>();
Arrays . sort (candidates);
dfs(rst , new ArrayList <>() , candidates , target , 0 , 0 ) ;
return rst;
}
private void dfs ( List < List < Integer >> rst , List < Integer > list , int [] nums , int target , int sum , int start){
if (sum > target) return ;
if (sum == target){
rst . add ( new ArrayList < Integer >(list));
return ;
}
for ( int i = start; i < nums . length ; i ++ ){
list . add (nums[i]);
dfs(rst , list , nums , target , sum + nums[i] , i + 1 ) ;
list . remove ( list . size () - 1 );
while (i + 1 < nums . length && nums[i] == nums[i + 1 ]) i ++ ;
}
}
}
Trivial problem.
Copy public class Solution {
public List < List < Integer >> combinationSum3 ( int k , int n) {
List < List < Integer >> rst = new ArrayList <>();
dfs(rst , new ArrayList <>() , n , k , 0 , 1 ) ;
return rst;
}
private void dfs ( List < List < Integer >> rst , List < Integer > list , int target , int k , int sum , int start){
if (sum > target || k < 0 ) return ;
if (sum == target && k == 0 ){
rst . add ( new ArrayList < Integer >(list));
return ;
}
for ( int i = start; i <= 9 ; i ++ ){
list . add (i);
dfs(rst , list , target , k - 1 , sum + i , i + 1 ) ;
list . remove ( list . size () - 1 );
}
}
}
题目换成这样了之后依然是一个搜索问题,但是有了新的有趣特性。
主要在于这题和之前的 combination sum 还不太一样,它把 [1,3] 和 [3,1] 这种重复搜索算成两个解。于是强行制造了 overlap subproblems.
于是这题用搜索解会 TLE,加个 hashmap 做记忆化搜索,立刻就过了。
24ms ,时间复杂度较高,不如下面那个迭代的写法速度快。
O(n^d),d代表得到 >= target 的搜索深度。
Copy public class Solution {
public int combinationSum4 ( int [] nums , int target) {
return dfs(nums , 0 , target , new HashMap < Integer , Integer >()) ;
}
private int dfs ( int [] nums , int curSum , int target , HashMap < Integer , Integer > map){
if (curSum > target) return 0 ;
if (curSum == target) return 1 ;
if ( map . containsKey (curSum)) return map . get (curSum);
int count = 0 ;
for ( int i = 0 ; i < nums . length ; i ++ ){
count += dfs(nums , curSum + nums[i] , target , map) ;
}
map . put (curSum , count);
return count;
}
}
论坛里还有比较有趣的迭代写法,只需要 3ms,原理和 climbing stairs 差不多,建一个大小等于 target + 1 的 array 代表多少种不同的方式跳上来,依次遍历即可。
时间复杂度 O(n * target) + O(n log n)
Copy public class Solution {
public int combinationSum4 ( int [] nums , int target) {
Arrays . sort (nums);
int [] res = new int [target + 1 ];
for ( int i = 1 ; i < res . length ; i ++ ) {
for ( int num : nums) {
if (num > i)
break ;
else if (num == i)
res[i] += 1 ;
else
res[i] += res[i - num];
}
}
return res[target];
}
}
原理和 climbing stairs 差不多,建一个大小等于 target + 1 的 array 代表多少种不同的方式跳上来,依次遍历即可。
时间复杂度 O(n * target)
注意这里内外循环的顺序不能错,要先按 sum 从小到大的顺序看,然后才是遍历每个元素。因为所谓 bottom-up,是相对于 sum 而言的,不是相对于已有元素的 index 而言的。
可以看到,在只取 min/max 的时候我们不同的循环顺序都能保证正确答案;但是求解的数量时,要以 target value 为外循环。
Copy public class Solution {
public int combinationSum4 ( int [] nums , int target) {
// dp[sum] = number of ways to get sum
int [] dp = new int [target + 1 ];
// initialize, one way to get 0 sum with 0 coins
dp[ 0 ] = 1 ;
for ( int j = 1 ; j <= target; j ++ ){
for ( int i = 0 ; i < nums . length ; i ++ ){
if (j - nums[i] >= 0 ) dp[j] += dp[j - nums[i]];
}
}
return dp[target];
}
}