[leetcode] 39. Combination Sum

質問リンク

https://leetcode.com/problems/combination-sum/

input & output

Example 1

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]

Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

Example 2

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3

Input: candidates = [2], target = 1
Output: []

Example 4

Input: candidates = [1], target = 1
Output: [[1]]

Example 5

Input: candidates = [1], target = 2
Output: [[1,1]]

Approach #1

/*
Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]

0) candidates[i]===target이면 res에 can[i]추가하고 최종배열에 바로 넣음
1) target-candidates[i]를 배열에서 찾는다.
2) 없으면, 한번더 candidates[i]를 빼고 배열에서 남은 숫자를 찾는다.
....
4) 있으면 res배열에 추가, 없으면 res배열 비운다.(시작할때 빈배열에서 시작하도록)
5) 백트래킹(?)

7/2=3
7
*/

Solution #1

var combinationSum = function(candidates, target) {
  const result = [];
  const list=[];
  backtracking(result, list, candidates, target, 0);
  return result;
};

// 2, 2, 2, 2
function backtracking(result, tempList, nums, remain, start) {
  //console.log(nums);
  if (remain < 0) return;
  else if (remain === 0) return result.push([...tempList]);
  console.log(tempList);
  for (let i=start; i<nums.length; i++) {
      tempList.push(nums[i]);
      backtracking(result, tempList, nums, remain-nums[i], i);
      tempList.pop();
  }
}

Time Complexity

O(C^T)
C: candidates.length
T: target size
候補長に従ってチェックを繰り返し、その要素がtargetを作成できる数字であるかを確認し、target数字となる組み合わせが現れるまで確認を続けます.
この時1 1 1 1 1 1...このように,1をtargetの大きさにすることは最も深い再帰であるため,時間的複雑さはC^Tとなる.

Space Complexity

O(T)->耳が一番深い時[1,1,1...]
T: target size
同様に、callスタックが最も深い場合は1、1、1...空間の複雑さはTなので

Solution #2

var combinationSum = function(candidates, target) { 
    const result=[];
    if(candidates.length===1 && candidates[0]>target) return result;
    let c=0;
    
    const dfs = (c,sum,arr) =>{
        // 타깃보다 크면 return;
        // 타깃과 같으면 정답에 추가하고 return;
        // 타깃보다 작으면 recursion
      if(c>=candidates.length) return;
      
      if(sum>target) return;
        
      if(sum===target){
          result.push([...arr]);
          return;
        }
        
      //recursion
      for(let i=c; i < candidates.length ; i++){
          arr.push(candidates[i]); //[2,2,2,1]
          dfs(i,sum+candidates[i],arr); // dfs(c,2,[2])
          arr.pop();
      }	
    };
      
      dfs(c,0,[]);
    
      return result;
  };

Time Complexity

O(C^T)
C: candidates.length
T: target size
候補長に従ってチェックを繰り返し、その要素がtargetを作成できる数字であるかを確認し、target数字となる組み合わせが現れるまで確認を続けます.
この時1 1 1 1 1 1...このように,1をtargetの大きさにすることは最も深い再帰であるため,時間的複雑さはC^Tとなる.

Space Complexity

O(T)->耳が一番深い時[1,1,1...]
T: target size
同様に、callスタックが最も深い場合は1、1、1...空間の複雑さはTなので