[LeetCode 연습 문제] Combination Sum

Combination Sum
Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
Note:

All numbers (including target) will be positive integers.

Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).

The solution set must not contain duplicate combinations.

For example, given candidate set 2,3,6,7 and target 7 , A solution set is: [7] [2, 2, 3]

주어진 집합 에서 Target 의 수 와 의 조합 을 찾 아 한 수 를 반복 해서 사용 할 수 있 습 니 다.
결과 집합 은 중복 되 지 않 으 며, 모든 결 과 는 오름차 순 으로 배열 된다.

문제 풀이 방향:
이것 은 아주 좋 은 문제 입 니 다. 역 추적 법 을 사 용 했 습 니 다. 시험 점 은 이전의 Permutation 과 약간 비슷 합 니 다.코드 가 비슷 한 점 이 있 습 니 다.
다음 수 를 만 날 때마다 target 보다 크 면 nums 가 정렬 되 어 있 기 때문에 일치 하지 않 을 것 입 니 다. 되 돌아 갑 니 다.
그렇지 않 으 면 이 숫자 를 pushback 중간 결과 로 돌아 가기 시작 합 니 다.재 귀적 이 끝 날 때 이 숫자 pop 을 꺼 내 이 위치 에서 다음 수 를 계속 시도 해 야 합 니 다.

코드 는 다음 과 같 습 니 다:

class Solution {

public:

    vector<vector<int> > combinationSum(vector<int> &nums, int target) {

        sort(nums.begin(),nums.end());

        vector<int> temp;  //    

        vector<vector<int>> result; //    

        dp(nums,0,target,temp,result);

        return result;

    }

    

    void dp(vector<int> &nums,int start,int target,vector<int> &temp,vector<vector<int>> &result){

        if(target == 0){   //         

            result.push_back(temp);

            return ;

        }

        

        for(int i = start; i < nums.size(); i++){  

            if(nums[i] > target){  //  

                return ;

            }

            temp.push_back(nums[i]);  //          

            dp(nums,i,target - nums[i],temp,result);

            temp.pop_back();  //  

        }

    }

};

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

python 문자열 입력으로 모든 유효한 IP 주소 생성(LeetCode 93번 문제)

이 문제의 공식 난이도는 Medium으로 좋아요 1296, 반대 505, 통과율 35.4%를 눌렀다.각 항목의 지표로 말하자면 보기에는 약간 규범에 맞는 것 같지만, 실제로도 확실히 그렇다.이 문제의 해법과 의도는 ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

[LeetCode 연습 문제] Combination Sum

좋은 웹페이지 즐겨찾기