조합 합계 Leetcode 솔루션  


난이도 중급
자주 묻는 질문 어도비 벽돌 Airbnb 아마존 Apple 골드 피처 블룸버그 게시물에서 ByteDance 이베이 페이스북 서비스 골드만 삭스 구글 링크드 인 Microsoft 신탁 Snapchat 사각형. 동네 짱 VM웨어 월마트 연구소
알고리즘 배열 역 추적 코딩 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions

Combination Sum Leetcode Solution이 제공하는 문제는 정렬 또는 정수 및 대상 목록. 주어진 목표에 합산되는 횟수에 관계없이 이러한 정수를 사용하여 만들 수있는 조합을 찾아야합니다. 좀 더 공식적으로 주어진 정수를 주어진 대상에 추가 할 수 있도록 몇 번이든 사용할 수 있습니다. 필요한 출력은 주어진 목표와 동일한 합계를 갖는 조합입니다.

조합 합계 Leetcode 솔루션  

candidates = [2,3,6,7], target = 7
[[2,2,3],[7]]

설명 : 주어진 출력이 주어진 목표에 합산됩니다. 우리가 다른 조합을 생각해 내려해도. 동일한 정수를 다른 순서로 배열하게됩니다. 그러나 순서는 조합 만 중요하지 않습니다.

candidates = [2,3,5], target = 8
[[2,2,2,2],[2,3,3],[3,5]]

설명 : 동일한 정수를 여러 번 사용할 수 있기 때문입니다. 출력에서는 첫 번째 출력에서 ​​2 번을 여러 번 사용했습니다. 마찬가지로 두 번째 출력에서 ​​2가 반복됩니다. 3 개의 출력이 모두 주어진 목표에 합산되는지 확인할 수 있습니다.

Combination Sum Leetcode 솔루션에 대한 접근 방식  

문제에 대한 접근 방식은 쉽게 찾을 수 있습니다. 일반적으로 이와 같은 문제에서는 역 추적을 사용해야합니다. 그러한 질문에서 우리는 완전한 검색을 수행하고 답을 찾아야하기 때문입니다. 그래서 먼저 우리에게 주어진 정수 목록을 정렬합니다. 그 후, 현재 임시 정수 목록에 정수를 계속 추가하고 주어진 대상에 더하기 위해 필요한 나머지 합계를 추적하는 재귀 함수를 만듭니다. 따라서 재귀 함수 내부에는 두 가지 기본 케이스가 있습니다. 첫 번째 기본 사례는 필요한 나머지 합계가 음수인지 확인하는 것입니다. 이 경우 재귀 함수에서 돌아갑니다. 두 번째 기본 케이스는 나머지 합계가 XNUMX 인 경우 필수 조건입니다. 나머지 합계가 XNUMX이면 필요한 목표에 도달했음을 의미합니다. 이 시점에서 현재 임시 정수 목록을 배열의 출력 배열로 푸시합니다.

참조
코인 변경 문제

암호  

Combination Sum Leetcode 솔루션을위한 C ++ 코드

#include <bits/stdc++.h>
using namespace std;

void backtrack(vector<vector<int>> &output, vector<int> &current, vector<int> &candidates, int remain, int start){
    if(remain < 0)
        return;
    else if(remain == 0)output.push_back(current);
    else {
        for(int i=start;i<candidates.size();i++){
            current.push_back(candidates[i]);
            backtrack(output, current, candidates, remain - candidates[i], i);
            current.pop_back();
        }
    }
}

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    vector<vector<int>> output;
    vector<int> current;
    sort(candidates.begin(), candidates.end());
    backtrack(output, current, candidates, target, 0);
    return output;
}

int main(){
  vector<int> cand = {2, 3, 6, 7};
  vector<vector<int>> output = combinationSum(cand, 7)	;
  for(auto x: output){
    for(auto y: x)
      cout<<y<<" ";
    cout<<endl;
  }
}
2 2 3 
7

Combination Sum Leetcode 솔루션을위한 Java 코드

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static 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 static 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);
          }
      }
  }

  public static void main (String[] args) throws java.lang.Exception
  {
    int[] nums = {2, 3, 6, 7};
    List<List<Integer>> output = combinationSum(nums, 7);
    for(List<Integer> x: output){
      for(Integer y: x)
        System.out.print(y+" ");
      System.out.println();
    }
  }
}
2 2 3
7

복잡성 분석  

시간 복잡성

O (N ^ (M / T + 1)) 여기서 N은 후보의 수이고 M은 주어진 모든 정수 중에서 가장 작은 후보이며 T는 목표 값입니다. 따라서 시간 복잡성은 기하 급수적이며 알고리즘이 재귀 적 역 추적이기 때문에 예상됩니다.

공간 복잡성

O (T / M), 여기서 T는 목표 값이고 M은 다른 모든 후보 중에서 최소 요소입니다.

1