Question

Formatted question description: https://leetcode.ca/all/39.html

39. Combination Sum

Level

Medium

Description

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

Note:

  • All numbers (including target) will be positive integers.
  • The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
  [7],
  [2,2,3]
]

Example 2:

Input: candidates = [2,3,5], target = 8,
A solution set is:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

Algorithm

DFS

Such a result requires the return of all the questions that meet the requirements to solve the problem, in all likelihood, it is necessary to use recursion.

And the idea of solving the problem is the same, similar questions include Path Sum II, Subsets II, Permutations, Permutations II, Combinations, etc. Here we add three new variables, start records the current recursive subscript, out is a solution, res saves everything that has been obtained The solution of each time a new recursive function is called, the target at this time must be subtracted from the current array.

DP

We can also use iterative solutions to create a three-dimensional array dp, where dp[i] represents the set of all solutions whose target number is i+1. Here i traverse from 1 to target. For each i, create a two-dimensional array cur, and then traverse the candidates array. If the number traversed is greater than i, it means that the current and subsequent numbers cannot form i, directly break off. Otherwise, if they are equal, the current numbers form an array by themselves and added to cur. Otherwise, traverse all the arrays in dp[i-candidates[j]-1]. If the current number is greater than the first element of the array, skip it, because the result is required to be in order. Otherwise, add the current number to the beginning of the array, and put the array into cur, see the code as follows:

Code

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;


public class Combination_Sum {

    public static void main(String[] args) {
        Combination_Sum out = new Combination_Sum();
        Solution_dp s = out.new Solution_dp();

//        System.out.println(s.combinationSum(new int[]{2,3,6,7}, 7)); // [[2,2,3],[7]]
        System.out.println(s.combinationSum(new int[]{2,3,5}, 8)); // [[2,2,2,2],[2,3,3],[3,5]]
    }

    class Solution {

        List<List<Integer>> result = new ArrayList<>();

        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            if (candidates == null || candidates.length == 0) {
                return result;
            }

            dfs(candidates, target, 0, new ArrayList<Integer>());

            return result;
        }

        private void dfs(int[] candidates, int target, int start, ArrayList<Integer> onePath) {

            if (start >= candidates.length || target < 0) { // target<0, assumption is all positive
                return;
            }

            if (target == 0) {
                result.add(new ArrayList<>(onePath));
                // continue, and possible 1,-1 are next ones
            }

            for (int i = start; i < candidates.length; i++) {
                System.out.println(i);
                onePath.add(candidates[i]);
                dfs(candidates, target - candidates[i], i, onePath);
                onePath.remove(onePath.size() - 1);
            }
        }
    }

    class Solution_dp {
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            // for each-target (from 1 to target), its dp[i][j] => so 3-D array dp[][][]
            List<List<List<Integer>>> dp = new ArrayList<>();
            Arrays.sort(candidates);

            for (int i = 1; i <= target; ++i) {
                List<List<Integer>> cur = new ArrayList<>();
                for (int j = 0; j < candidates.length; ++j) {
                    if (candidates[j] > i) break;
                    if (candidates[j] == i) {
                        ArrayList<Integer> one = new ArrayList<Integer>();
                        one.add(candidates[j]);
                        cur.add(one); // @note: one with proper <Integer>, or else unsupoorted operation error
                        break;
                    }
                    for (List<Integer> a : dp.get(i - candidates[j] - 1)) {
                        if (candidates[j] > a.get(0)) {
                            continue;
                        }

                        ArrayList<Integer> deepCopied = new ArrayList<>(a); // @note: must have
                        deepCopied.add(0, candidates[j]); // @note: largest at index=0 for the array
                        cur.add(deepCopied);
                    }
                }
                dp.add(cur);
            }

            return dp.get(dp.size() - 1);
        }

    }
}

All Problems

All Solutions