TopCoder ： AB problem

Problem Statement

You are given two s: N and K. Lun the dog is interested in strings that satisfy the following conditions:

• The string has exactly N characters, each of which is either 'A' or 'B'.
• The string s has exactly K pairs (i, j) (0 <= i < j <= N-1) such that s[i] = 'A' and s[j] = 'B'.

If there exists a string that satisfies the conditions, find and return any such string. Otherwise, return an empty string.

Definition

Class:

AB

Method:

createString

Parameters:

int, int

Returns:

String

Method signature:

String createString(int N, int K)

(be sure your method is public)

Limits

Time limit (s):

2.000

Memory limit (MB):

256

Constraints

- N will be between 2 and 50, inclusive.

- K will be between 0 and N(N-1)/2, inclusive.

Examples

0)

3

2

Returns: "ABB"

This string has exactly two pairs (i, j) mentioned in the statement: (0, 1) and (0, 2).

1)

2

0

Returns: "BA"

Please note that there are valid test cases with K = 0.

2)

5

8

Returns: ""

Five characters is too short for this value of K.

3)

10

12

Returns: "BAABBABAAB"

Please note that this is an example of a solution; other valid solutions will also be accepted.

A:
就是递归（DFS），没想到什么太简单的解法。

import java.util.Arrays;

public class AB{
    boolean findRes = false;
    public String createString(int N, int K){
        char AB [] = new char[N];
        // for each potential number of B
        for(int nB = 0;nB<N;nB++) // number of B
            helper(AB,0,  nB, K);
        return findRes? new String(AB) : "";
        
    }
    private void helper(char[] AB, int start,  int nB, int K){
        int N = AB.length;
        if(findRes==true)
               return;
        if(K<0 || nB<0|| nB > (N-start))
            return;
        if(K==0 && nB == N-start){
            Arrays.fill(AB,start, N, 'B');
            findRes = true;
            return;
        }
           // try to fillin one position at AB[start]
        AB[start] = 'A';
        helper(AB,start+1,nB, K-nB);
        AB[start] = 'B';
        helper(AB,start+1,nB-1, K);
        
    }
}