인프런 커뮤니티 질문&답변
작성한 질문수
부분집합 전역변수 질문
작성
·
8
0
public class Subsets {
List<List<Integer>> ans = new ArrayList<>();
List<List<Integer>> solution(int[] nums, int m) {
dfs(nums, m, 0, new ArrayList<>());
return ans;
}
void dfs(int[] nums, int m, int start, List<Integer> curr) {
//base case
ans.add(new ArrayList<>(curr)); // 매순간 ans에 추가
//상태 전이
for(int i=start; i< nums.length; i++) {
curr.add(nums[i]);
dfs(nums, m, i+1, curr);
curr.remove(curr.size()-1);
}
}
}ans를 전역변수로 설정하고 for문으로 상태 전이할때마다 ans값을 수정하는 방식으로 구현할때
addAll(dfs(nums, m, i+1, curr));으로 하니 dfs가 void로 리턴돼서 에러가 나는데
위의 코드 블럭과 같이 dfs(nums, m, i+1, curr);로 실행하고 basecase에서만 ans에 curr을 추가하는 방식으로 하면 되는걸까요?
질문 봐주셔서 감사합니다!
답변 2
0
네, 지금 전역변수 코드 너무 잘 짜셨습니다!
addAll 쓰면 dfs의 리턴값이 void라서 에러가 나는게 맞고요!!
basecase도 잘 하셨습니다~
잘하시네요. 전역변수를 안쓴 버전도 한번 해보시면 도움이 많이 될겁니다 :)
0
안녕하세요, 인프런 AI 인턴입니다. ming님!
주신 코드에서 dfs 메서드는 기본적인 백트래킹 알고리즘을 통해 부분집합을 생성하고 있습니다. 여기서 각 함수 호출 때마다 현재 상태를 ans 리스트에 추가하고 있습니다.
부분집합 문제에 대한 핵심 이해:
- 재귀적으로 부분집합을 탐색하면서 각 재귀 호출은 curr 리스트에 현재 상태까지의 부분집합을 포함시킵니다.
- curr 상태가 정해질 때마다 이 상태를 새로운 리스트로 만들어 ans에 추가합니다.
코드 블록 안에서 addAll(dfs(nums, m, i+1, curr));으로 하면서 발생하는 에러는 dfs 함수가 void로 정의되어 있어 값을 반환하지 못하는 것 때문입니다. 대신, 주어진 코드처럼 재귀 함수 호출 자체에서 결과를 리스트에 추가하는 방식은 적절합니다.
관련 게시물 링크:
이와 비슷한 상황에서 부분집합 문제의 해답을 찾는 예제를 포함하고 있는 유사한 답변 게시물을 추천드립니다. 직접적으로 도움이 되실 수 있습니다.
완전탐색 - 구현(순열) 질문
여기서는 순열의 구현에 대해 설명하고 있습니다. 구조는 다르지만, 백트래킹의 원리를 이해하는 데 도움이 될 수 있습니다.시간복잡도 질문
백트래킹과 반복문에 대한 기초적인 이해를 제공하여 시간복잡도를 이해하는 데 도움이 됩니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.