leetcode 39. 조합 총화C++_med_질문

1911 단어 데이터 구조
중복 요소 가 없 는 배열 을 지정 합 니 다.  candidates  목표 수  target  ,찾아내다  candidates  숫자  target  라 는 조합 을 만 들 었 다.candidates  중의 숫자 는 무제 한 중복 으로 선택 할 수 있다.
설명:
모든 숫자 (포함)  target) 모두 정수 이다
4. 567917. 해 집 은 중복 되 는 조합 을 포함 할 수 없습니다. 
예시 1:
  : candidates = [2,3,6,7], target = 7,
     :
[
  [7],
  [2,2,3]
]

예시 2:
  : candidates = [2,3,5], target = 8,
     :
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

 
사고방식: 조합 문제 와 배열 문 제 는 주로 역 추적 법 으로 문 제 를 해결한다 (사실은 모든 상황 을 판단 해 야 한다).역 추적 법 은 바로 재 귀 이 고 관건 은 재 귀 함수 와 재 귀 의 종료 조건 을 찾 는 것 이다.이 문 제 는 candidates 의 한 수 a 를 선택 하여 candidates 에 target - a 가 존재 하 는 지 판단 하 는 것 입 니 다. 어떻게 판단 할 까요? 한 수 를 계속 꺼 내 서 안에 target - a - b 를 모 을 수 있 는 지 판단 하 는 것 입 니 다................................................................또 하나의 작은 디 테 일 은 중복 되 는 데이터 세트 가 있어 서 는 안 되 기 때문에 되 찾 을 수 없다.재 귀 가 끝 난 후 마지막 가입 수 를 어디서 지 웁 니까?
C + + 코드 는 다음 과 같 습 니 다.
class Solution {
    vector> res;
    
    //sum          ,p          ,start           。
    void findSum(const vector& candi, const int& target,int sum,vector& p,int start)
    {
        if(sum == target)
        {
            res.push_back(p);
            return;
        }
        if(sum > target)
            return;
        for(int i=start;i> combinationSum(vector& candidates, int target) {
        res.clear();
        if(candidates.size() == 0) return res;
        vector p;
        findSum(candidates,target,0,p,0);
        return res;
    }
};

좋은 웹페이지 즐겨찾기