[자바 알고리즘 인터뷰] 12장 그래프 (5) 조합의 합

https://leetcode.com/problems/combination-sum/description/

 

 

 

- 숫자 집합 candidates를 조합하여 합이 target이 되는 엘리먼트들을 나열하라. 각 숫자는 중복으로 나열 가능하다. 

 

 

풀이 1) DFS로 중복 조합 그래프 탐색 

 

 

- 합 target을 만들 수 있는 모든 번호 조합을 찾는 문제인데, 앞서 순열 문제와 유사하게 DFS로 풀이할 수 있다. 

- 입력값의 중복 조합 그래프를 풀이하는 문제로 도식화할 수 있다. 

 

출처 : 자바 알고리즘 인터뷰 with 코틀린 저자:박상길 <책만>

 

- 모든 중복 조합에서 찾아야 하기 때문에 항상 부모의 값부터 시작하는 그래프로 구성할 수 있다. 

- 조합은 각각의 노드가 자기 자신보다 더 큰 숫자의 나열로 정리할 수 있다. 

 

 public void dfs(List<List<Integer>> results, int candidates[], int target, int index, Deque<Integer> path)
 {
     //0보다 작다면 목푯값을 넘어섰으므로 리턴
     if(target<0)
         return;
     //0이면 목푯값에 도달했으므로 결과에 추가하고 리턴
     if(target==0)
     {
         //이전 경로를 저장해둔 path를 결과에 삽입
         results.add(new ArrayList<>(path));
         return;
     }
     //자기 자신보다 큰 숫자를 DFS 진행
     for(int i=index; i<candidates.length; i++)
     {
         //path에 현재 엘리먼트 추가
         path.add(candidates[i]);
         //재귀 dfs
         dfs(results,candidates,target-candidates[i],i,path);
         //돌아온 이후에는 현재 엘리먼트 삭제
         path.removeLast();
     }
 }

 

 

- dfs로 재귀 호출하되, dfs() 함수에서 파라미터 index는 현재 순서, 예를 들어 [2,3,5,8]에서 현재 5에서 탐색을 진행 중이라면 index는 2가 된다 . 

- path는 지금까지 탐색한 경로를 저장한다. 

- 재귀 dfs를 진행하기 전에 현재 엘리먼트를 저장하고, 탐색을 끝내고 되돌아오면 바로 직전에 저장한 엘리먼트를 삭제한다. 

 

종료 조건 

1) target<0 인 경우 

 - 목푯값을 초과한 경우로 탐색을 종료한다. 

 

2) target = 0 인 경우 

 - 목푯값과 일치하므로 정답이다.

 - 결과 변수에 정답을 추가하고 탐색을 종료한다.

 

 

 

class Solution {
    public void dfs(List<List<Integer>> results, int candidates[], int target, int index, Deque<Integer> path)
    {
        //0보다 작다면 목푯값을 넘어섰으므로 리턴
        if(target<0)
            return;
        //0이면 목푯값에 도달했으므로 결과에 추가하고 리턴
        if(target==0)
        {
            //이전 경로를 저장해둔 path를 결과에 삽입
            results.add(new ArrayList<>(path));
            return;
        }
        //자기 자신보다 큰 숫자를 DFS 진행
        for(int i=index; i<candidates.length; i++)
        {
            //path에 현재 엘리먼트 추가
            path.add(candidates[i]);
            //재귀 dfs
            dfs(results,candidates,target-candidates[i],i,path);
            //돌아온 이후에는 현재 엘리먼트 삭제
            path.removeLast();
        }
    }

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        //결과 저장 리스트 선언
        List<List<Integer>> results = new ArrayList<>();
        //dfs 시작
        dfs(results, candidates, target, 0, new ArrayDeque<>());

        return results;
        
    }
}

 2밀리초 

 

 

중복 순열 

순열, 중복순열, 조합, 중복조합을 Java에서 구현해보자 | Young Jin's Blog (jhy0285.github.io)

순열, 중복순열, 조합, 중복조합을 Java에서 구현해보자

 

- 주어진 n개 중에서 r개를 뽑은 순서쌍의 모든 경우의 수 

 

import java.util.*;

class Solution
{
	//각 순서쌍을 저장할 리스트 선언
    static List<int[]> answer = new ArrayList<>();
    
	public static void main(String args[]) throws Exception
	{
		//순서쌍을 저장하기 위한 변수
		int permu[] = new int[2];
		
		int target[] = new int[] {100,200,300,400};
		
		//중복 순열 재귀함수
		dfs(target,2,0,permu);
		
		//함수가 끝나면 경우의 수랑 각 순서쌍 출력
		System.out.printf("총 경우의 수:%d가지",answer.size());
		System.out.println();
		for (int[] ans : answer) {
            System.out.println(Arrays.toString(ans));
        }

	}
	
	public static void dfs(int target[], int R, int cnt, int permu[])
	{
		//cnt는 순서쌍의 순서 위치를 의미
		//따라서 cnt==R이라면 이미 0~R-1 즉 R개가 뽑힌 것이므로 순서쌍을 저장하고 재귀를 끝낸다
		if(cnt==R)
		{
			answer.add(permu.clone());
			return;
		}
		
		for(int i=0; i<target.length; i++)
		{
			permu[cnt] = target[i];
			//모든 경우의 수를 구하되, 순서 위치만 1씩 더해준다, 
			dfs(target,R,cnt+1,permu);
		}
	}
}