두 개 뽑아서 더하기

🔗 문제 링크

https://programmers.co.kr/learn/courses/30/lessons/68644

❔ 문제 설명

정수 배열 numbers가 주어집니다. numbers에서 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아 return 하도록 solution 함수를 완성해주세요.

⚠️ 제한사항

• numbers의 길이는 2 이상 100 이하입니다.

• numbers의 모든 수는 0 이상 100 이하입니다.

💡 풀이 (언어 : Java)

단순 이중 반복문으로도 조건이 빡세지 않아 성공할 수 있는 문제이지만, 조합을 가지고 풀 수 있는 문제라서 공부를 해보았다. DFS를 이용해서 두가지 경우로 계속 분기하면서 숫자가 2개가 될때까지 수를 고르고 리스트에 같은 값이 있는지 확인후에 없으면 넣어주고 마지막에 정렬해주고 반환해주는 알고리즘이다. 조합은 순서와 상관없이 고르는 경우의 수이므로 각각의 고르는 차례마다 해당 인덱스의 수를 고르거나, 고르지 않거나 2가지의 경우로 나누어서 계속 재귀함수를 호출한다. 숫자가 2개가 되거나 길이가 전체 숫자만큼 되면 종료한다.

class Solution {
    ArrayList<Integer> answer = new ArrayList<>();

    public void dfs(int idx, int cnt, int sum, int[] numbers) {
        if (cnt == 2) {
            if (!answer.contains(sum))
                answer.add(sum);
            return;
        }
        if (idx != numbers.length) {
            dfs(idx + 1, cnt + 1, sum + numbers[idx], numbers);
            dfs(idx + 1, cnt, sum, numbers);
        }
    }

    public ArrayList<Integer> solution(int[] numbers) {
        dfs(0, 0, 0, numbers);
        Collections.sort(answer);
        return answer;
    }
}