Baekjun No. 15651, N and M (3) (with.Java)

This is an article about Baekjun No. 15651, N and M(3) (with.Java).

I want to solve the coding test problem, find out how to solve it differently from the retrospective of the problem I solved, and get to know.

Let’s get to the problem first.

Problem

Write a program to find all sequences of length M that satisfy the following conditions, given the natural numbers N and M.

• A sequence of M selected from natural numbers from 1 to N.
• You can choose the same number several times.

Input

The number of test cases T is given in the first line.

Each test case consists of a line, given an integer n.

n is positive and less than 11.

Output

For each test case, output the number of methods to express n as the sum of 1, 2, and 3.

problem solving

import java.io.*;
import java.util.StringTokenizer;

class Main{
    public static int N, M;
    public static int[] arr;
    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        br.close();


        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[M];

        dfs(0);

        bw.flush();
        bw.close();
    }

    public static void dfs(int depth) throws Exception{
        if(depth == M){
            for (int i = 0; i < M; i++){
                bw.write(arr[i] + " ");
            }
            bw.write("\n");
            return;
        }

        for(int i = 1; i <= N; i++){
            arr[depth] = i;
            dfs(depth + 1);
        }
    }
}

Solution Description

This code is a program that uses backtracking to generate and output M permutations consisting of numbers from 1 to N.

First, use ‘BufferedReader’ to receive input, and use ‘StringTokenizer’ to parse two spaces separated integers N and M.

N represents the range of numbers to select from, and M represents the length of the permutation to output.

Close ‘BufferedReader’ after processing the input.

Array ‘arr’ is an integer array of size M, which is responsible for storing permutations currently being configured.

Then, call ‘dfs(0)’ to start a depth-first search (DFS).

The ‘dfs’ method is a recursive function that performs backtracking. This function takes the current ‘depth’ value as a factor, and when ‘depth’ is equal to M, the value stored in ‘arr’ is outputted using ‘BufferedWriter’.

At this time, each number is separated by a space, and each time a permutation is completed, a permutation character is added.

Select the numbers from 1 to N sequentially through the iteration and store them in ‘arr[depth]’, then call ‘dfs(depth + 1)’ to move to the next depth.

This will allow you to explore the number of cases that allow duplication.

After all DFS calls are terminated, empty and close the buffer of the ‘BufferedWriter’ to complete the output operation.

This allows for efficient generation and output of all permutations of length M that allow for duplicate numbers.