Leetcode #39. Combination Sum 조합 구문 및 문제 풀이 보고서
1 문제 풀이 사상
원제는 몇 개의 숫자와 하나의 목표 값을 정하고 이 숫자들 중에서 몇 개를 골라 합치면 그의 합은 목표 값과 딱 같고 그 중 한 개의 숫자는 여러 번 선택할 수 있다는 것이다.출력을 요구하는 것은 중복될 수 없고 그룹 내의 순서는 내림차순으로 할 수 없습니다.
이 문제는 우선 반드시 생각해야 할 것이 정렬이다. 정렬은 매우 기본적이고 자주 사용하는 조작이다.
그리고 우리는 중복을 배제해야 한다. (한 수를 중복해서 선택할 수 있으므로 중복은 먼저 없애는 것이 가장 좋다. 왜냐하면 우리는 역추적을 해야 하기 때문이다. 이렇게 하면 무의미한 비용을 낮출 수 있기 때문이다.)
그 다음에 우리는 해답을 구하기 시작했다. 해답을 구하는 방법은 귀속의 거슬러 올라가는 것이다. 매번 귀속 전달에 필요한 수치reserve를 사용하고 이미 선택한 숫자를 기록하는 것이다. 원칙적으로 현재 선택한 숫자는 이전보다 크기 때문에 index는 어느 색인부터 선택할 수 있는지 표시한다.
그리고reserve가 0이면 최종 결과에 가입하고, 못 만나면 추가하지 않습니다~~
2 원제
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]
3 AC 해제
public class Solution {
/** * ， ， reserve=0 list * **/
int n;
int nums[];
List<List<Integer>> result;
// ， ，
public void find(List<Integer> values,int index,int reserve){
if(reserve==0){
ArrayList<Integer> item=new ArrayList<Integer>();
item.addAll(values);
result.add(item);
}
for(int i=index;i<n;i++){
if(nums[i]<=reserve){
values.add(nums[i]);
find(values,i,reserve-nums[i]);
values.remove(values.size()-1);
}
}
}
public List<List<Integer>> combinationSum(int[] candidates, int target) {
//
Arrays.sort(candidates);
// ，
int i,j,k,n;
n=1;
for(i=1;i<candidates.length;i++){
if(candidates[i]!=candidates[i-1]){
candidates[n++]=candidates[i];
}
}
this.nums=candidates;
this.n=n;
this.result=new ArrayList<List<Integer>>();
find(new ArrayList<Integer>(),0,target);
return this.result;
}
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
