leetcode 40 조합수 총계 2
16478 단어 거슬러 올라가다
처음에는 이렇게 썼지만 중복되는 현상이 발견되어 수조를 정렬하고 거슬러 올라가는 과정에서 판단조건을 추가하여 무겁게 했다.
class Solution {
List<List<Integer>> res = new ArrayList<>();
boolean vis[];
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
vis = new boolean[candidates.length];
List<Integer> path = new ArrayList<>();
helper(0, target, candidates, path);
return res;
}
private void helper(int id, int target, int[] nums, List<Integer> path){
if (id == nums.length) return;
if (target == 0){
res.add(new ArrayList<>(path));
return;
}
helper(id + 1, target, nums, path);
if (target >= nums[id] && !vis[id]){
vis[id] = true;
path.add(nums[id]);
helper(id, target - nums[id], nums, path);
vis[id] = false;
path.remove(path.size() - 1);
}
}
}
AC 코드가 앞의 값과 같고 앞의 값이 사용되지 않으면 현재 id를 선택하는 상황을 고려했기 때문에 건너뛸 수 있습니다.
class Solution {
List<List<Integer>> res = new ArrayList<>();
boolean vis[];
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
vis = new boolean[candidates.length];
Arrays.sort(candidates);
List<Integer> path = new ArrayList<>();
helper(0, target, candidates, path);
return res;
}
private void helper(int id, int target, int[] nums, List<Integer> path){
if (id == nums.length) return;
if (target == 0){
res.add(new ArrayList<>(path));
return;
}
if (id > 0 && nums[id] == nums[id - 1] && !vis[id - 1]){
helper(id + 1, target, nums, path);
return;
}
if (target >= nums[id] && !vis[id]){
vis[id] = true;
path.add(nums[id]);
helper(id, target - nums[id], nums, path);
vis[id] = false;
path.remove(path.size() - 1);
}
helper(id + 1, target, nums, path);
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Leetcode #39. Combination Sum 조합 구문 및 문제 풀이 보고서원제는 몇 개의 숫자와 하나의 목표 값을 정하고 이 숫자들 중에서 몇 개를 골라 합치면 그의 합은 목표 값과 딱 같고 그 중 한 개의 숫자는 여러 번 선택할 수 있다는 것이다.출력을 요구하는 것은 중복될 수 없고 그...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
