Problem & Approach

  • 39. Combination Sum I

    It’s the easiest one among problems of Combination Sum. We could use backtracking to solve this one.

  • 40. Combination Sum II

    It’s similar to the previous Combination-sum-I. However, the most imporant different point is that it’s required these answers to be unique. So, we can use the method mentioned in Combination-sum-I with some changes. In order to avoid the same answers, we have to skip some elements in backtracking process. As for some element, we need to skip elements behind this one.

  • 216. Combination Sum III

    It’s similar to Combination Sum I. Backtracking is enough.

  • 377. Combination Sum IV

    Every element in the array can be used in zero or many times just like Combination Sum I. But if use that method for I, it will TLE. Besides this reason, it isn’t required for us to compute every answer what it is. We just need the number of answers. So, we can let DP[target] defines as the number of possible combinations. Then, DP[i] += DP[i - nums[k]], 0 <= k < nums.length.

Code

  1. problem 1 
    class Solution {
 public List<List<Integer>> combinationSum(int[] candidates, int target) {
     Arrays.sort(candidates);
     List<List<Integer>> ans = new ArrayList<>();
     helper(candidates, 0, target, 0, new Stack<Integer>(), ans);
     return ans;
 }
 public void helper(int[] nums, int index, int target, int sum, Stack<Integer> stack, List<List<Integer>> ans){
     if(sum == target){
         ans.add(new ArrayList(stack));
         return ;
     }
     for(int i = index; i < nums.length; i ++){
         if(sum + nums[i] <= target){
             stack.push(nums[i]);
             helper(nums, i, target, sum + nums[i], stack, ans);
             stack.pop();
         }
         else{
             break;
         }
     }
 }
}
  2. problem 2 
    class Solution {
 public List<List<Integer>> combinationSum2(int[] candidates, int target) {
     Arrays.sort(candidates);
     List<List<Integer>> ans = new ArrayList<>();
     helper(candidates, 0, target, 0, new Stack<Integer>(), ans);
     return ans;
 }
 public void helper(int[] nums, int index, int target, int sum, Stack<Integer> stack, List<List<Integer>> ans){
     if(sum == target){
         ans.add(new ArrayList(stack));
         return ;
     }
     for(int i = index; i < nums.length; i ++){
         if(sum + nums[i] <= target){
             stack.push(nums[i]);
             int curNum = nums[i];
             helper(nums, i + 1, target, sum + curNum, stack, ans);
             stack.pop();
             while(i + 1 < nums.length && nums[i] == nums[i + 1]){
                 i ++;
             }
         }
         else{
             break;
         }
     }
 }
}
  3. problem 3 
    class Solution {
 public void helper(int k, int index, int sum, int target, List<Integer> cur, List<List<Integer>> ans){
     if(k == 0){
         if(sum == target){
             ans.add(new ArrayList<Integer>(cur));
         }
         return ;
     }
     for(int i = index + 1; i <= 9; i ++){
         if(sum + i <= target){
             cur.add(i);
             helper(k - 1, i, sum + i, target, cur, ans);
             cur.remove(cur.size() - 1);
         }
     }
 }
        
 public List<List<Integer>> combinationSum3(int k, int n) {
     List<List<Integer>> ans = new ArrayList<>();
     helper(k, 0, 0, n, new ArrayList<Integer>(), ans);
     return ans;
 }
}
  4. problem 4 
    class Solution {
 public int combinationSum4(int[] nums, int target) {
     int N = nums.length;
     if(N == 0) return 0;
     int[] dp = new int[target + 1];
     dp[0] = 1;
     for(int i = 1; i <= target; i ++){
         for(int num: nums){
             if(num <= i){
                 dp[i] += dp[i - num];
             }
         }
     }
     return dp[target];
 }
}