[알고리즘]수 분할

n이 주워질 때

더해서 n을 만들 수 있는 경우의 수를 구해라

 

ex) n = 4

1+1+1+1 = 4

1+1+2 = 4

1+2+1 = 4

1+3 = 4

2+1+1 = 4

2+2 = 4

3+1 =4

 

7가지 경우의 수

 

---

package com.company;

import java.util.Arrays;

public class 수분할 {

    public void solution(int n){

        int[] a = new int[n];

        dfs(a, n, n, 0);

    }

    public void dfs(int[]array, int remainder, int n, int index){
        if(remainder == 0){
            System.out.println(Arrays.toString(array));
            return;
        }

        for(int i = 1; i < n; i++){
            if(remainder - i < 0) continue;

            array[index] = i;
            dfs(array, remainder - i, n, index + 1);
            array[index] = 0;

        }

    }

}

결과

핵심 코드, 푸는법:

재귀(완전탐색)