39. Combination Sum.md

39. Combination Sum

---

leetcode-cn Daily Challenge on September 9th, 2020.

leetcode Daily Challenge on October 2rd, 2020.

---

Difficulty : Medium

Related Topics : Array、Backtracking

---

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]
]

Constraints:

• 1 <= candidates.length <= 30
• 1 <= candidates[i] <= 200
• Each element of candidate is unique.
• 1 <= target <= 500

---

Solution

• mine

  • Java

    same as 40. Combination Sum II and 216. Combination Sum III.

    • Recursive & Backtrack Runtime: 2 ms, faster than 99.51%, Memory Usage: 39.5 MB, less than 91.69% of Java online submissions

      //O(?)time   O(?)space
      public List<List<Integer>> combinationSum(int[] candidates, int target) {
          Arrays.sort(candidates);
          List<List<Integer>> res = new ArrayList<>();
          if (candidates.length == 0 || candidates[0] > target) {
              return res;
          }
          res = recursive(candidates, target, 0);
          return res;
      }
      
      public List<List<Integer>> recursive(int[] arr, int target, int start) {
          List<List<Integer>> res = new ArrayList<>();
      
          if (start >= arr.length || arr[start] > target) {
              return res;
          }
          if (target == arr[start]) {
              List<Integer> t = new ArrayList<>();
              t.add(arr[start]);
              res.add(t);
              return res;
          }
      
          for (int j = start; j < arr.length; j++) {
              if (target == arr[j]) {
                  List<Integer> t = new ArrayList<>();
                  t.add(arr[j]);
                  res.add(t);
                  break;
              }
              List<List<Integer>> temp = recursive(arr, target - arr[j], j);
              if (!temp.isEmpty()) {
                  for (List<Integer> t : temp) {
                      t.add(0, arr[j]);
                      res.add(t);
                  }
              }
          }
          return res;
      }
      

    • Runtime: 3 ms, faster than 84.12%, Memory Usage: 39.8 MB, less than 65.80% of Java online submissions

      public List<List<Integer>> combinationSum(int[] candidates, int target) {
          Arrays.sort(candidates);
          List<List<Integer>> res = new LinkedList<>();
          helper(res, candidates, target, new ArrayList<>());
          return res;
      }
      
      void helper(List<List<Integer>> res, int[] arr, int target, List<Integer> temp) {
          if (target < 0) return;
          for (int num : arr) {
              if (num > target) return;
              if (temp.size() > 0 && temp.get(temp.size() - 1) > num) continue;
              if (num == target) {
                  List<Integer> t = new LinkedList<>();
                  t.addAll(temp);
                  t.add(num);
                  res.add(t);
              } else {
                  temp.add(num);
                  helper(res, arr, target - num, temp);
                  temp.remove(temp.size() - 1);
              }
          }
      }
      

---

• the most votes

• Backtracking Runtime: 5 ms, faster than 39.18%, Memory Usage: 39.2 MB, less than 25.93% of Java online submissions

  public List<List<Integer>> combinationSum(int[] nums, int target) {
      List<List<Integer>> list = new ArrayList<>();
      Arrays.sort(nums);
      backtrack(list, new ArrayList<>(), nums, target, 0);
      return list;
  }
  
  private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int remain, int start){
      if(remain < 0) return;
      else if(remain == 0) list.add(new ArrayList<>(tempList));
      else{
          for(int i = start; i < nums.length; i++){
              tempList.add(nums[i]);
              backtrack(list, tempList, nums, remain - nums[i], i); // not i + 1 because we can reuse same elements
              tempList.remove(tempList.size() - 1);
          }
      }
  }
  

---