LeetCode 377 - Combination Sum IV


Related: LeetCode 39 - Combination Sum
Leetcode 216 Combination Sum III
Leetcode 216 Combination Sum III
https://www.hrwhisper.me/leetcode-combination-sum-iv/
Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.
Example:
nums = [1, 2, 3]
target = 4

The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Note that different sequences are counted as different combinations.

Therefore the output is 7.
Follow up:
What if negative numbers are allowed in the given array?
How does it change the problem?
What limitation we need to add to the question to allow negative numbers?
X. DP
http://blog.csdn.net/fantasiasango/article/details/52034809
https://discuss.leetcode.com/topic/52186/my-3ms-java-dp-solution
  1.     public int combinationSum4(int[] nums, int target) {  
  2.         int[] dp = new int[target+1];  
  3.         Arrays.sort(nums);  
  4.         dp[0] = 1;  
  5.         for(int i = 1; i <= target; i++){  
  6.             for(int j = 0; j < nums.length; j++){  
  7.                 if(nums[j] > i) break;  
  8.                 dp[i] += dp[i - nums[j]];  
  9.             }  
  10.         }  
  11.         return dp[target];  
  12.     }  

  1.     public int combinationSum4(int[] nums, int target) {  
  2.         int[] dp= new int[target+1];  
  3.         dp[0] = 1;  
  4.         for(int i = 1; i <= target;i++){  
  5.             for(int num:nums){  
  6.                 if(i >= num) dp[i] += dp[i - num];  
  7.             }  
  8.         }  
  9.         return dp[target];  
  10.     }  
https://discuss.leetcode.com/topic/52302/1ms-java-dp-solution-with-detailed-explanation/
Think about the recurrence relation first. How does the # of combinations of the target related to the # of combinations of numbers that are smaller than the target?
So we know that target is the sum of numbers in the array. Imagine we only need one more number to reach target, this number can be any one in the array, right? So the # of combinations of targetcomb[target] = sum(comb[target - nums[i]]), where 0 <= i < nums.length, and target >= nums[i].
In the example given, we can actually find the # of combinations of 4 with the # of combinations of 3(4 - 1), 2(4- 2) and 1(4 - 3). As a result, comb[4] = comb[4-1] + comb[4-2] + comb[4-3] = comb[3] + comb[2] + comb[1].
Then think about the base case. Since if the target is 0, there is only one way to get zero, which is using 0, we can set comb[0] = 1.
EDIT: The problem says that target is a positive integer that makes me feel it's unclear to put it in the above way. Since target == 0only happens when in the previous call, target = nums[i], we know that this is the only combination in this case, so we return 1.
Now we can come up with at least a recursive solution.
public int combinationSum4(int[] nums, int target) {
    if (target == 0) {
        return 1;
    }
    int res = 0;
    for (int i = 0; i < nums.length; i++) {
        if (target >= nums[i]) {
            res += combinationSum4(nums, target - nums[i]);
        }
    }
    return res;
}
Now for a DP solution, we just need to figure out a way to store the intermediate results, to avoid the same combination sum being calculated many times. We can use an array to save those results, and check if there is already a result before calculation. We can fill the array with -1 to indicate that the result hasn't been calculated yet. 0 is not a good choice because it means there is no combination sum for the target.
private int[] dp;

public int combinationSum4(int[] nums, int target) {
    dp = new int[target + 1];
    Arrays.fill(dp, -1);
    dp[0] = 1;
    return helper(nums, target);
}

private int helper(int[] nums, int target) {
    if (dp[target] != -1) {
        return dp[target];
    }
    int res = 0;
    for (int i = 0; i < nums.length; i++) {
        if (target >= nums[i]) {
            res += helper(nums, target - nums[i]);
        }
    }
    dp[target] = res;
    return res;
}
EDIT: The above solution is top-down. How about a bottom-up one?
public int combinationSum4(int[] nums, int target) {
    int[] comb = new int[target + 1];
    comb[0] = 1;
    for (int i = 1; i < comb.length; i++) {
        for (int j = 0; j < nums.length; j++) {
            if (i - nums[j] >= 0) {
                comb[i] += comb[i - nums[j]];
            }
        }
    }
    return comb[target];
}
One minor improvement I can think of is to use res[0]. Assume empty list is putting zero elements in a list. So there is 1 way to create empty list. This will help remove the check if n is equal to i or not.

X. DP - Presort
http://www.cnblogs.com/grandyang/p/5705750.html
如果target远大于nums数组的个数的话,上面的算法可以做适当的优化,先给nums数组排个序,然后从1遍历到target,对于i小于数组中的数字x时,我们直接break掉,因为后面的数更大,其余地方不变.
public int combinationSum4(int[] nums, int target) {
    Arrays.sort(nums);
    int[] res = new int[target+1];
    res[0]=1; // 1 way to create empty combination.
    for(int i=0 ;i<=target; i++)
    {
        for(int n : nums)
        {
            if(n>i) break;
            res[i]+=res[i-n];
        }
    }
    return res[target];
}
X. DP -Push
https://www.programcreek.com/2014/07/leetcode-combination-sum-iv-java/
public int combinationSum4(int[] nums, int target) {
    if(nums==null || nums.length==0)
        return 0;
 
    int[] dp = new int[target+1];
 
    dp[0]=1;
 
    for(int i=0; i<=target; i++){
       for(int num: nums){
           if(i+num<=target){
               dp[i+num]+=dp[i];
           }
       }
    }
 
    return dp[target];
}

X. Memory search: Top Down
good solution, but some cases such as
[100000000,200000000,300000000]
1400000000
will get Memory Limit Exceeded due to you assign the length of "res" array as target+1,
to avoid that we could use Memory optimization search
    HashMap<Integer, Integer> hashmap;
 
 public int combinationSum4(int[] nums, int target)
 {
  int len=nums.length;
  Arrays.sort(nums);
  hashmap=new HashMap<>(len);
  search(nums, target);
  return hashmap.get(target);
 }
 
 public int search(int[] nums,int target)
 {
  if(hashmap.containsKey(target))
   return hashmap.get(target);
  
  int index=Arrays.binarySearch(nums, target);
  boolean exist=index>=0;
  if(index<0)
   index=-(index+1);
  
  int sum=(exist?1:0);
  
  for(int i=index-1;i>=0;i--)
  {
   int dis=target-nums[i];
   sum+=search(nums, dis);
  }
  
  hashmap.put(target, sum);
  return sum;
 }

    Map<Integer, Integer> map = new HashMap<>();
    public int combinationSum4(int[] nums, int target) {
        int count = 0;
        if (nums == null || nums.length ==0 || target < 0 ) return 0;
        if ( target ==0 ) return 1;
        if (map.containsKey(target)) return map.get(target);
        for (int num: nums){
            count += combinationSum4(nums, target-num);
        }
        map.put(target, count);
        return count;
    }

X. Follow up
The problem with negative numbers is that now the combinations could be potentially of infinite length. Think about nums = [-1, 1]and target = 1. We can have all sequences of arbitrary length that follow the patterns -1, 1, -1, 1, ..., -1, 1, 1 and 1, -1, 1, -1, ..., 1, -1, 1 (there are also others, of course, just to give an example). So we should limit the length of the combination sequence, so as to give a bound to the problem.
https://discuss.leetcode.com/topic/52290/java-follow-up-using-recursion-and-memorization
In order to allow negative integers, the length of the combination sum needs to be restricted, or the search will not stop. This is a modification from my previous solution, which also use memory to avoid repeated calculations.
Map<Integer, Map<Integer,Integer>> map2 = new HashMap<>();
    private int helper2(int[] nums, int len, int target, int MaxLen) {
     int count = 0;
        if (  len > MaxLen  ) return 0;
        if ( map2.containsKey(target) && map2.get(target).containsKey(len)) { 
         return map2.get(target).get(len);
        }
        if ( target == 0 )   count++;
        for (int num: nums) {
            count+= helper2(nums, len+1, target-num, MaxLen);
        }
        if ( ! map2.containsKey(target) ) map2.put(target, new HashMap<Integer,Integer>());
        Map<Integer,Integer> mem = map2.get(target);
        mem.put(len, count);
        return count;
    }
       
    public int combinationSum42(int[] nums, int target, int MaxLen) {
        if (nums == null || nums.length ==0 || MaxLen <= 0 ) return 0;
        map2 = new HashMap<>();
        return helper2(nums, 0,target, MaxLen);
    }

题意:给定一个元素互不相同且均为正数的数组,让你用该数组中的数组合成target(可以重复使用),问有多少种。
思路:DP可以有两种
  • dp[i] += dp[i-num]
  • dp[i+num] += dp[i]
    public int combinationSum4(int[] nums, int target) {
        int[] dp= new int[target+1];
        dp[0] = 1;
        for(int i = 1; i <= target;i++){
            for(int num:nums){
                if(i >= num) dp[i] += dp[i - num];
            }
        }
        return dp[target];
    }

    public int combinationSum4(int[] nums, int target) {
        int[] dp= new int[target+1];
        dp[0] = 1;
        for(int i = 0; i < target;i++){
            for(int num:nums){
                if(i + num <= target) dp[i + num] += dp[i];
            }
        }
        return dp[target];
    }
http://blog.csdn.net/yeqiuzs/article/details/52029034
  1. public int combinationSum4(int[] nums, int target) {  
  2.     int dp[] = new int[target + 1];  
  3.     for (int i = 0; i <= target; i++) {  
  4.         for (int k = 0; k < nums.length; k++) {  
  5.             if (i - nums[k] > 0) {  
  6.                 dp[i] += dp[i - nums[k]];  
  7.             } else if (i - nums[k] == 0) {  
  8.                 dp[i] += 1;  
  9.             }  
  10.   
  11.         }  
  12.     }  
  13.     return dp[target];  
  14. }  
如果target远大于nums数组的个数的话,上面的算法可以做适当的优化,先给nums数组排个序,然后从1遍历到target,对于i小于数组中的数字x时,我们直接break掉,因为后面的数更大,其余地方不变
Because in the loop for (int num: nums) {} we have a break;. Actually if the nums is not sorted, we could continuewhen num > i, the code could still pass the tests.
    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];
    }
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> dp(target + 1);
        dp[0] = 1;
        sort(nums.begin(), nums.end());
        for (int i = 1; i <= target; ++i) {
            for (auto a : nums) {
                if (i < a) break;
                dp[i] += dp[i - a];
            }
        }
        return dp.back();
    }
private int[] dp;

public int combinationSum4(int[] nums, int target) {
    dp = new int[target + 1];
    Arrays.fill(dp, -1);
    dp[0] = 1;
    return helper(nums, target);
}

private int helper(int[] nums, int target) {
    if (dp[target] != -1) {
        return dp[target];
    }
    int res = 0;
    for (int i = 0; i < nums.length; i++) {
        if (target >= nums[i]) {
            res += helper(nums, target - nums[i]);
        }
    }
    dp[target] = res;
    return res;
}

public int combinationSum4() {
    if (target == 0) {
        return 1;
    }
    int res = 0;
    for (int i = 0; i < nums.length; i++) {
        if (target >= nums[i]) {
            res += combinationSum4(nums, target - nums[i]);
        }
    }
    return res;
}
Why not removing that if statement inside the for loop and substitute with a if (target <= 0) return not target; base case? The code would be clearer and shorter.
Follow up:
有负数的情况可能存在无限符合要求的解。(比如你想想有个-1的,我正数随便加,然后再减回去)
所以必须要有限制条件,限制条件有很多啊 比如要求解的长度为L,或者不超过L,或者每个数只能使用X次等等

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts