python 3.5

A = 'abcdefghijklmnopqrstuvwxyz'

def itoa(s, n):
    if n == '':
        print(s)
        return None
    itoa(s + A[int(n[0]) - 1], n[1:])
    if len(n) >= 2 and int(n[0:2]) <= 26:
        itoa(s + A[int(n[0:2]) - 1], n[2:])

>>> itoa('', '1123')
aabc
aaw
alc
kbc
kw

(let [result (atom nil)]
  (defn distribute
    ([digits]
     (reset! result [])
     (distribute digits [])
     @result)
    ([[a b :as digits] acc]
     (cond (nil? a) (swap! result #(conj % acc))
           (nil? b) (distribute (rest digits)
                                (conj acc a))
           :else (do (distribute (rest digits)
                                 (conj acc a))
                     (distribute (drop 2 digits)
                                 (conj acc (+ (* 10 a) b))))))))
(defn facebook [n]
  (let [alpha-n? #(and (<= 1 %) (<= % 26))
        digits   (map #(Character/getNumericValue %) (str n))
        dists    (distribute digits)
        alphas   (filter #(every? alpha-n? %) dists)
        n->c     #(char (+ 0x60 %))
        ->string #(apply str (map n->c %))]
    (map ->string alphas)))

Clojure 코드입니다. 재귀 함수로 찾아낸 조합들을 추출하는 게 어려워서 상태 변수(distribute 함수에 클로저로 바인딩 된 atom)를 사용했어요. Scheme 보다는 Common Lisp 스타일이죠. 리스프 잘 하시는 분들이 보시면 눈쌀을 확 찌푸리실 것 같네요.

해결 방법

1) 다음과 같은 재귀 함수를 만들어 분배 조합들을 찾았습니다.

이 함수의 이름을 distribute라고 할 때 다음 두 경우의 조합을 생성합니다.

• (주어진 리스트의 첫 번째 원소) + (나머지 원소들의 distribute)

• (주어진 리스트의 (첫 번째 원소 + 두 번째 원소)) + (세번째 이후 원소들의 distribute)

함수는 자신이 거쳐 온 수들의 누적 리스트를 갖고 있다가 가지의 끝에 다다르면 그것을 반환용 콘테이너에 집어 넣습니다.

모든 재귀 호출이 끝나면, 각 가지들의 결과 조합을 모두 모아서 반환합니다.

2) 위 함수를 통해 분배 조합들을 모두 구한 뒤, 1 ~ 26 이외의 값을 포함한 조합들을 제거하였습니다.

테스트

=> (facebook 1123)
("aabc" "aaw" "alc" "kbc" "kw")

=> (facebook 11111)
("aaaaa" "aaak" "aaka" "akaa" "akk" "kaaa" "kak" "kka")

=> (facebook 12345)
("abcde" "awde" "lcde")

=> (facebook 12321)
("abcba" "abcu" "awba" "awu" "lcba" "lcu")

=> (facebook 2221)
("bbba" "bbu" "bva" "vba" "vu")

파이썬3.4

seperate_with_comma(1123) : 콤마로 나눌수있는 모든 리스트를 제너레이터 합니다.
[[1123], [112, 3], [11, 23], [11, 2, 3], [1, 123], [1, 12, 3], [1, 1, 23], [1, 1, 2, 3]]
convert_to_text(lists) : 인수로 받은 리스트들을 매핑된 숫자범위에 따라 글자로 변환합니다.
['kw', 'kbc', 'alc', 'aaw', 'aabc']

*콤마로 나눌수있는 리스트는 숫자가 커지면 굉장히 많아지기 때문에 제너레이터로 하나씩 yield했습니다.

from string import ascii_lowercase
from itertools import product, zip_longest

abc_map = {num: abc for num, abc in enumerate(ascii_lowercase, 1)}

def seperate_with_comma(num):
    "seperate_with_comma(1123) -> [[1123], [112, 3], [11, 23], [11, 2, 3], ...]"
    num = str(num)
    length = len(num) - 1
    result = ''
    num_with_x = list(zip_longest(num, 'x' * length, fillvalue='')) #[('1', 'x'), ('1', 'x'), ('2', 'x'), ('3', '')]
    num_product = product(range(2), repeat=length) #(0, 0, 0), (0, 1, 0), ... (1, 1, 1)
    #itertools.compress 함수를 비슷하게 흉내내었습니다. 0이면 '', 1이면 ','로 변환합니다.
    for np in num_product:
        for num_x, or_0_1 in zip_longest(num_with_x, np, fillvalue=''):
            num, x = num_x
            if or_0_1:
                x = ','
            else:
                x = ''
            result += num + x
        yield list(int(n) for n in result.split(','))
        result = ''


def convert_to_text(lists):
    "[11, 2, 3] -> 'kbc'"
    for items in lists:
        if all(item <= 23 for item in items):
            yield ''.join(abc_map[item] for item in items)

list(convert_to_text(seperate_with_comma(1123)))
#['kw', 'kbc', 'alc', 'aaw', 'aabc']

매칭되는 글자가 있으면 뒷부분에 대해서 같은 문제를 풀고 맨 앞에 그 글자를 덧붙이기만 하면 되죠.

$dict = (1..26).map{|e| /^#{e}/}.zip('a'..'z')


def recurs(s)
    return [""] if s.empty?

    results = []
    $dict.each do |pat|
        next if s !~ pat[0]     
        next_s = s.sub(pat[0], "")      

        results.concat recurs(next_s).map{|e| pat[1] + e } 
    end
    results
end

p recurs("1123")
p recurs("11111")
p recurs("12345")
p recurs("12321")
p recurs("2221")

public class FacebookProblem {

    private HashMap<String, String> convertMap = new HashMap<String, String>();

    public FacebookProblem() {
        for (int i = 1; i <= 26; i++) {
            convertMap.put(Integer.toString(i), new Character((char)(i + 96)).toString());
        }
    }

    public static void main(String[] args) {
        FacebookProblem fp = new FacebookProblem();

        SortedSet<String> result = new TreeSet<String>();

        fp.getAllString("1123", new ArrayList<String>(), result);
        System.out.println(result);

    }


    /**
     * 
     * @param input : 입력으로 들어오는 string
     * @param tokenList : prefix 들의 연결
     * @param result : 알파벳으로 변환된 값
     * 
     * 1. 입력으로 들어오는 문자열의 prefix 결과들을 가져온다.
     * 2. 해당 prefix 을 제외하고 나며지를 입력으로 해서 재귀적으로 호출한다.
     * 3. 입력으로 들어오는 문자열이 empty string 일때, 변환한다.
     * 
     */
    public void getAllString(String input, List<String> tokenList, SortedSet<String> result) {
        if (input.equals("")) {
            String strResult = "";
            for (String token : tokenList) {
                if (convertMap.containsKey(token)) {
                    strResult += convertMap.get(token);
                } else {
                    return;
                }
            }

            result.add(strResult);
            return;
        }

        List<String> prefixList = getPrefixList(input);
        for (String prefix : prefixList) {
            String remain = input.substring(prefix.length());
            tokenList.add(prefix);
            getAllString(remain, tokenList, result);
            tokenList.remove(tokenList.size() - 1);
        }
    }

    private List<String> getPrefixList(String input) {
        List<String> prefixList = new ArrayList<String>();

        for (int i = 0; i < input.length(); i++) {
            prefixList.add(input.substring(0, i + 1));
        }

        return prefixList;
    }
}

재귀로 풀어보았습니다.

python.

def n2a(n):
    alpha = "abcdefghijklmnopqrstuvwxyz"
    if 1<=n<=26:
        return alpha[n-1]
    return ""


def num2str(num):
    result = []
    def run(num, cur=""):
        if len(num) >= 1:
            head = n2a(int(num[0]))
            r = run(num[1:], cur+head)
            if r: result.append(r)

        if len(num) >= 2 and int(num[0:2]) < 26:
            head = n2a(int(num[0:2]))
            r = run(num[2:], cur+head)
            if r: result.append(r)

        if not num:
            return cur
    run(num)
    return result


print num2str("1123")
print num2str("12312")

이 문제는 쉽게 풀 수도 또 어려운 문제일 수 있습니다. 메모리 생각하지 않고 그냥 풀면 이렇게 간단하게 풀 수 있습니다. 해시 테이블 하나 둬서 메모이제이션하면 되겠지만 일부러 안 했고요. 만약 이 문제를 리스트 병합(메모리 많이 먹을 수 있음)없이 출력만 하는 것이 목표라면(추가 메모리 사용 거의 없이) 좀 까다로울 수 있습니다. 보통 페이스북 문제라고 해서 이 수준까지만 풀면 안 됩니다. 아마 더 제한 조건을 줄겁니다.

Python 2.7

def numToChar(n):
  return chr(ord('a') + int(n) - 1)

def findAllStrings(input):
  if len(input) < 1:
    return ['']
  elif len(input) == 1:
    return [numToChar(input[0])]

  result = [numToChar(input[0]) + s for s in findAllStrings(input[1:])]
  if int(input[:2]) <= 26:
    result += [numToChar(int(input[:2])) + s for s in findAllStrings(input[2:])]
  return result

print findAllStrings("1123")

Sub Main()
        Dim input As Integer = CInt(Val(Console.ReadLine))

        Rcv({}, input, input)

        Console.ReadLine()
    End Sub

    Public Sub Rcv(f() As String, n As String, org As String)
        If n.Length = 0 Then Return

        Dim apb() As Char = Array.ConvertAll(Enumerable.Range(97, 26).ToArray, Function(d As Integer) Chr(d))

        Dim a As Integer = n.Substring(0, 1)
        Dim b As Integer = n.Substring(0, Math.Min(2, n.Length))
        Dim fs As String = String.Join("", f.Select(Function(d As String) apb(CInt(d) - 1)))

        If a < apb.Count And
            String.Join("", f) & a = org Then
            Console.WriteLine(fs & apb(a - 1))
        End If

        If (a <> b And b < apb.Count) And
            String.Join("", f) & b = org Then
            Console.WriteLine(fs & apb(b - 1))
        End If

        Dim _f() As String = f.Clone

        ReDim Preserve _f(_f.Length) : _f(_f.Length - 1) = a
        Rcv(_f, n.Substring(1, n.Length - 1), org)

        If a <> b And b < apb.Count Then
            ReDim Preserve f(f.Length) : f(f.Length - 1) = b
            Rcv(f, n.Substring(2, n.Length - 2), org)
        End If
    End Sub

재귀함수가 좀 더럽네요 ㅜ

• python으로 작성 하였습니다.

import string

alphabets=[None];alphabets.extend(string.ascii_lowercase)

def getChr(idx,s,e):

    if idx==len(s):
        print "".join(alphabets[int(c)] for c in e)
        return

    if idx+1<len(s) and int(s[idx:idx+2]) <=26:
        a=e[:];a.append(int(s[idx:idx+2]))
        getChr(idx+2,s,a)

        b=e[:];b.append(int(s[idx]))
        getChr(idx+1,s,b)
    else: 
        c=e[:];c.append(int(s[idx]))
        getChr(idx+1,s,c)

getChr(0,"11234",[])

def one(n): return chr(ord('a')+int(n)-1)
def chrize(n):
    res =()
    if len(n) == 0 : return ('',)
    if len(n) == 1 : return one(n),
    res += tuple(one(n[0])+e for e in chrize(n[1:]))
    if int(n[:2])<27 : res += tuple(one(n[:2])+e for e in chrize(n[2:]))
    return res

while 1:
    n = raw_input()
    for word in set(chrize(n)):print word
    print

Ruby

다시 풀어봤습니다.

ch = ('1'..'26').zip('a'..'z').to_h
head = ->n { [1,2].map {|i| [n[i..-1]||"", ch[n[0,i]]] }.uniq.select {|_,c|c} }
gens = ->num,s="" { num[0] ? head[num].flat_map {|n,c| gens[n, s+c] } : s }

Test

expect( gens['1123'] ).to eq ["aabc", "aaw", "alc", "kbc", "kw"]
expect( gens['12321'] ).to eq ["abcba", "abcu", "awba", "awu", "lcba", "lcu"]
expect( gens['12345'] ).to eq ["abcde", "awde", "lcde"]
expect( gens['129981'] ).to eq ["abiiha", "liiha"]

Output

#=> puts gens[gets.chop]
1123

aabc
aaw
alc
kbc
kw

li = [];a = list(chr(x) for x in range(97,123))
def ch(n):global a;return a[int(n)-1]
def c(s,n):global li;li.append(s + ch(n))
def find(n, s = ''):
    if n[0] == '0':return
    #0이 처음수면 리턴
    if len(n) == 1:c(s, n);return
    #한자리수면 카운트
    elif len(n) == 2:
        if n[1] == '0':c(s, n);return
        if n[0] in ['1','2']:
            find(n[1:], s+ch(n[0]))
            c(s, n);return
        else:find(num[1:], s+ch(n[0]))
    #두자리수면 재귀 안하고 카운트
    elif len(n) > 2:
        if n[1] == '0':find(n[2:],s+ch(n[:2]));return
        if n[0] in ['1','2']:
            find(n[1:], s+ch(n[0]))
            find(n[2:], s+ch(n[:2]))
        else:find(n[1:], s+ch(n[0]))
    #세자리수 이상이면 재귀

파이썬 3.5.1입니다. 불가능한 숫자 넣어도 작동합니다.

재귀로 풀어보았습니다.

def do(s, prefix=""):
    if len(s) == 0:
        print(prefix)
        return
    for j in range(1,len(s)+1):
        x = int(s[0:j])
        if 0 < x < 27:
            do(s[j:], prefix=prefix+chr(x+96))
        else:
            break
do('1123')

재귀로 간결하게 해결 가능합니다. C++로 코딩했는데 string 객체와 map 자료구조를 사용했습니다. 출력하는 순서에 대한 설명이 없어서 그냥 만들 수 있는 문자열을 무작위로 출력하게 했습니다. 제 프로그램에 1123을 넣으면

kw

kbc

alc

aaw

aabc

를 출력합니다. 아래는 제 코드입니다.

#include <iostream> 
#include <cstdlib>
#include <string> 
#include <sstream> 
#include <map> 
using namespace std;

map<int,char> mp; 

int toInt(string s){
    int n; 
    istringstream iss (s); 
    iss >> n; 
    return n; 
}

void recur(string number,string s){
    if (number.size() == 0){
        cout << s << endl;
        return; 
    }
    if ((int)number.size() - 2 >= 0) recur(number.substr(2),s+mp[toInt(number.substr(0,2))]); 
    if ((int)number.size() - 1 >= 0) recur(number.substr(1),s+mp[toInt(number.substr(0,1))]); 
} 


int main(){
    for (int i = 1; i <= 26; i++){ // map 초기화 
        mp[i] = char('a'+i-1);  
    }
    string number;  
    cin >> number;  
    recur(number,"");  
    return 0; 
}

Delphi 2010 무식하게 모든 경우의 수로 직접찾기

procedure fnNumberToAlpabets(str: string; sList: TStrings);
var
  i, j, j2, f, k, k1, k2, t, nA, cnt, found, grp: Integer;
  V: array [0 .. 100] of Integer;
  s: string;
begin
  nA := Ord('a') - 1;
  cnt := Length(str);
  for i := 1 to cnt do
    V[i] := StrToInt(str[i]);

  // 쌍수가 0 인 경우
  grp := cnt div 2; // 쌍수의 최대의 수임. 3까지만 처리
  for f := 0 to grp do
    case f of
      0:
        begin //
          s := '';
          for i := 1 to cnt do
            s := s + Char(V[i] + nA);
          sList.Add(s);
        end;
      1:
        begin // Grop이 한개인 경우
          for i := 1 to cnt - 1 do
          begin
            k := 1;
            s := '';
            while k <= cnt do
            begin
              if i = k then // 쌍처리
              begin
                t := V[k] * 10 + V[k + 1];
                if t > 26 then
                begin
                  s := '';
                  break;
                end;
                Inc(k);
                s := s + Char(t + nA);
              end
              else
              begin
                s := s + Char(V[k] + nA);
              end;
              Inc(k);
            end;
            if s <> '' then
              sList.Add(s);
          end;
        end;
      2:
        begin // Grop이 두개인 경우
          for i := 1 to cnt - 2 do
            for j := i + 2 to cnt - 1 do
            begin
              s := '';
              k := 1;
              while k <= cnt do
              begin
                if (i = k) or (j = k) then // 쌍처리
                begin
                  t := V[k] * 10 + V[k + 1];
                  if t > 26 then
                  begin
                    s := '';
                    break;
                  end;
                  Inc(k);
                  s := s + Char(t + nA);
                end
                else
                begin
                  s := s + Char(V[k] + nA);
                end;
                Inc(k);
              end;

              if s <> '' then
                sList.Add(s);
            end;
        end;
      3:
        begin // Grop이 3인 경우
          for i := 1 to cnt - 4 do
            for j := i + 2 to cnt - 2 do
              for j2 := j + 4 to cnt - 1 do
              begin
                s := '';
                k := 1;
                while k <= cnt do
                begin
                  if (i = k) or (j = k) or (j2 = k) then // 쌍처리
                  begin
                    t := V[k] * 10 + V[k + 1];
                    if t > 26 then
                    begin
                      s := '';
                      break;
                    end;
                    Inc(k);
                    s := s + Char(t + nA);
                  end
                  else
                  begin
                    s := s + Char(V[k] + nA);
                  end;
                  Inc(k);
                end;

                if s <> '' then
                  sList.Add(s);
              end;
        end;
    end;
end;

procedure TForm4.btn숫자문자열Click(Sender: TObject);
var
  s: string;
begin
  s := '1123';
  Memo1.Lines.Add('Input : ' + s);
  fnNumberToAlpabets(s, Memo1.Lines);

  s := '11111';
  Memo1.Lines.Add('Input : ' + s);
  fnNumberToAlpabets(s, Memo1.Lines);

  s := '12345';
  Memo1.Lines.Add('Input : ' + s);
  fnNumberToAlpabets(s, Memo1.Lines);

  s := '12321';
  Memo1.Lines.Add('Input : ' + s);
  fnNumberToAlpabets(s, Memo1.Lines);

  s := '2221';
  Memo1.Lines.Add('Input : ' + s);
  fnNumberToAlpabets(s, Memo1.Lines);
end;

파이썬3.5

룰루랄라님과 길가의풀님의 코드를 그대로 갖다 붙였습니다.
재귀를 클로저로 구현하면 print를 쓰지 않아도 되고, 전역변수 쓸일이 없으므로
이런 문제에 궁합이 잘 맞다고 생각해요

def f(s):

    abc = lambda x: chr(x + 96)
    result = []

    def g(s, cur=''):

        if not s:
            return cur

        for i in range(1, len(s)+1):
            x = int(s[:i])

            if 1 <= x <= 26:
                r = g(s[i:], cur+abc(x))    
                if r: result.append(r)

            else:
                break

    g(s)    
    return result


if __name__ == '__main__':
    s = input()
    for x in f(s):
        print(x)

main으로 뼈대를 삼아보자. 그런데 출력할 값이 여러개이므로.. 콜백을 넘겨서 여러번 호출해줄 수 있다.

int main(int argc, const char * argv[]) {
    char* s = "1123";
    numtoalpha(s, puts);
    return 0;
}

numtoalpha는 입력 숫자문자열을 알파문자열로 바꿔서 모든 경우에 대해 콜백을 호출해주면 된다. 앞에서부터 숫자를 읽어서 알파벳으로 바꾸고 남은 숫자문자열도 마찬가지로 진행해야 한다. 그런데 1 => a고 11 => k 처럼 한글자를 처리할 수도 두글자를 처리할 수도 있으니까 각각의 경우를 depth first search처럼 탐색하면 될것 같다.

depth first search는 보조함수 만들고, 출력할 문자열을 담을 버퍼도 하나 준비해서 던져줘야 한다. 버퍼는 입력된 숫자문자열보다 길지 않다.

void numtoalpha(char* s, void (*f)(char* )) {
    char *buf = (char*)malloc(strlen(s) + 1);
    numtoalpha_(s, buf, 0, f); // 0은 buf에 채워진 글자 수 
    free(buf);
}

보조함수 numtoalpha_는 입력문자열 s가 끝났으면 현재 버퍼를 콜백으로 처리해주고 아니면 한글자 혹은 두글자 처리하여 재귀 계속 진행..

void numtoalpha_(char* s, char* buf, int i, void (*f)(char*)) {
    if (s[0] == 0) {
        buf[i] = 0;
        f(buf);
    } else {
        //... 한글자 혹은 두글자 처리
    }
}

a=1, z=26이므로 첫글자가 0이 될 수 없다.

if (s[0] == '0') return;

한글자만 먼저 처리하면.. 숫자글자를 정수로 바꾸고, 그 정수를 알파벳으로 바꾼다.

int num = s[0] - '0';
char alpha = 'a' + num - 1; // num 이 1 이면 'a'

이제 버퍼에 한글자 채우고 depth first 진행.

buf[i] = alpha;
numtoalpha_(s+1, buf, i+1, f); // s 한글자 처리, buf에 한글자 추가

두글자인 경우도 처리해야 함. 그런데, 26보다 크면 말이 안됨.

num = (s[0] - '0') * 10 + (s[1] - '0');
if (num > 26) return;
alpha = 'a' + num - 1;
buf[i] = alpha;
numtoalpha_(s+2, buf, i+1, f); // s는 두글자 처리

끝!

aabc
aaw
alc
kbc
kw

재귀함수를 이용 하여 2개 씩 짝지은 모든 경우

그러나 허접한 알고리즘이기에 중복이 많아 중복 제거를 위해 string.h를 사용해야만 했다 ㅠㅠ

input : 1 1 2 3 size : 4 nbinding : 2

aabc kbc alc aaw kw

input : 1 1 2 3 5 size : 5 nbinding : 2

aabce kbce alce aawe kwe

input : 1 1 2 3 5 6 size : 6 nbinding : 3

aabcef kbcef alcef aawef kwef

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

struct Map {
    int ival;
    char cval;
}map[26];

int size;
char **out;
int count=0;

void mapping();
int* binding(int* arr, int nbinding, int tsize);

void main() {

    int input = 112356;
    mapping();

    int* arr;
    size = 0;
    int k=1;
    while(input/k!=0){
        k=k*10;
        size++;
    }
    arr = (int*) malloc (sizeof(int) * size);
    out = (char**) malloc (sizeof(char*) * size);
    int index=0;
    for(int i=size-1;i>=0;i--) {
        arr[index] = input/(int)pow(10.0, i);
        index++;
        input = input%(int)pow(10.0, i);
    }

    printf("input : ");
    for(int i=0;i<size;i++)
        printf("%d ", arr[i]);
    printf("\nsize : %d\n", size);
    int nbinding = size/2;
    printf("nbinding : %d\n", nbinding);
    printf("\n\n");

    for(int i=0 ;i<=nbinding ;i++) {
        binding(arr, i, size);
    }
    for(int i=0;i< count;i++)
        for(int j=0;j<count;j++)
            if(i!=j && 0==strcmp(out[i], out[j])){
                out[j] = "";
            }

    for(int i=0;i< count;i++)
        if(out[i]!=NULL)
            printf("%s\n", out[i]);
}

int* binding(int* arr, int nbinding, int tsize) {

    if(nbinding==0) {
        out[count] = (char*) malloc (sizeof(char) * tsize);
        for(int i=0;i<tsize;i++)
            out[count][i] = map[arr[i]-1].cval;
        out[count][tsize] = '\0';
        count++;
        return arr;
    }

    tsize--;
    int* temp = (int*) malloc (sizeof(int) * tsize);
    nbinding--;

    bool b = false;
    for(int i=0;i<size;i++) {
        int k = 0;
        for(int j=0; j<tsize ;j++) {
            if(arr[k]*10+arr[k+1]<=26 && arr[k]<10 && arr[k+1]<10 && i==j) {
                temp[j] = arr[k]*10+arr[k+1];
                k++;
                b = true;
            }
            else
                temp[j] = arr[k];
            k++;
        }
        if(b==true)
            binding(temp, nbinding, tsize);
        b=false;
    }
}

void mapping() {
    for(int i=0 ;i<26; i++) {
        map[i].ival = i+1;
        map[i].cval = i+97;
    }
}

#include <iostream>
#include <vector>
#include <math.h>
using namespace std;

char word[] = {"abcdefghijklmnopqrstuvwxyz"};

void num2word(int num_idx, vector < int > number, vector < char > ch) 
{
    int i, ch_idx=0;

    if(num_idx >= number.size())
    {   
        for( i=0; i<ch.size(); i++)
        {
            cout<<ch[i];
        }
        cout<<endl;
        return;
    }   

    for(i=0; i<2; i++)
    {   
        ch_idx = number[num_idx]*((int)pow(10,i)) + number[num_idx+i]*i;
        if(ch_idx < 26) 
        {
            ch.push_back(word[ch_idx-1]);
            num2word(num_idx+i+1, number, ch);
            ch.pop_back();
        }
    }   
    return;
}

int main ()
{
    vector < char > ch; 
    vector < int > numbers;
    string number_str;
    cin>>number_str;
    for(int i=0; i< number_str.length(); i++)
        numbers.push_back(number_str.at(i) - '0');
    num2word(0, numbers, ch);
}

중간에 0이 있거나 26보다 큰 수가 있을 때는 skip 하도록 처리했습니다.

그렇게 처리하고 보니 같은 문자열이 여러개 나오는 경우가 있어서

결과리스트 자료구조를 Set 으로 하였습니다.

javascript(ES6)

var strFromNum = function(n) {
    var input = ("" + n);
    var result = new Set();
    var alphabet = "abcdefghijklmnopqrstuvwxyz";

    var itoa = function itoa(i, a) {
        if (i === "") {
            result.add(a);
            return;
        }

        var index = 0;

        index = parseInt(i.substr(0, 1));
        itoa(i.substr(1), a + (alphabet[index - 1] || ""));

        index = parseInt(i.substr(0, 2));
        if (i.length >= 2) {
            itoa(i.substr(2), a + (alphabet[index - 1] || ""));
        }
    }

    itoa(input, "");

    return Array.from(result);
}

console.log(strFromNum(1123).join("\n"));
> aabc
> aaw
> alc
> kbc
> kw

console.log(strFromNum(10001).join("\n"));
> aa
> ja

console.log(strFromNum(12345).join("\n"));
> abcde
> abc
> abe
> awde
> aw
> lcde
> lc
> le

alpha = "abcdefghijklmnopqrstuvwxyz"

def itoc(n, s):
    if n is 0:
        print(s)
        return

    try:
        itoc(n//10, alpha[n%10-1] + s)
        if n > 10:
            itoc(n//100, alpha[n%100-1] + s)
    except:
        pass

[Python 3.6]

def findMapStr(inputStr):
    dic = " abcdefghijklmnopqrstuvwxyz"

    def makeMapStr(input, mapStr):
        if not input: print(mapStr); return

        makeMapStr(input[1:], mapStr + dic[int(input[0])])
        if(len(input) > 1 and int(input[:2]) <= 26): makeMapStr(input[2:], mapStr + dic[int(input[:2])])

    makeMapStr(inputStr, "")

inputStr = "1123"
findMapStr(inputStr)

import Control.Monad

solution :: [Int] -> [String]
solution = fmap (fmap (toEnum . (+ 96)) . reverse) . (foldM branch <$> pure.head <*> tail)
    where branch (x:xs) d = filter ((<=26).head) [d:(x:xs), (x*10 + d) : xs]

> solution [1,1,2,3]
["aabc","aaw","alc","kbc","kw"]

string ConvertToAlphabet(string& number)
{
    if (number.size() == 0) return "";
    char alp = stoi(number) + 'a' - 1;
    return string(1,alp);
}

void Print(string prefix, string currentNum)
{
    int currentNumLength = currentNum.size();

    if (currentNumLength > 0 && currentNum[0] == '0') //불가능한 루트
        return;

    if (currentNumLength <= 1)
    {
        cout << prefix + ConvertToAlphabet(currentNum) << endl;;
        return;
    }

    if ((currentNum[0] == '1')
        || (currentNum[0] == '2' && currentNum[1] < '7'))
    {
        Print(prefix + ConvertToAlphabet(currentNum.substr(0, 2)),
            currentNum.substr(2, currentNumLength));
    }

    Print(prefix + ConvertToAlphabet(currentNum.substr(0, 1)),
        currentNum.substr(1, currentNumLength));
}

package makeString;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Change(new Scanner(System.in).nextLine());
    }

    private static void Change(String num) {
        if (num.replaceAll("[^0-9]", "").equals(""))
            System.out.println(num);
        else {
            String temp = num.replaceAll("[^0-9]", "");
            if (temp.length() > 1 && Integer.valueOf(temp.substring(0, 2)) < 27)
                Change(num.replaceAll("[^a-z]", "") + (char) (Integer.valueOf(temp.substring(0, 2)) + 96)
                        + temp.substring(2));
            Change(num.replaceAll("[^a-z]", "") + ((char) (Integer.valueOf(temp.substring(0, 1)) + 96))
                    + temp.substring(1));
        }
    }
}

def xxx(n):
    n = str(n)
    al = lambda x: chr(96+int(x))
    conv = lambda x: ''.join(chr(96+int(i)) for i in x)

    if n == '': return ['']
    if len(n) == 1: return [al(n)]

    r = [conv(n)]

    for i in range(len(n)-1):
        k = bin(0b11 << i)[2:].zfill(len(n)).find('1')
        if int(n[k:k+2]) > 26: continue
        for m1 in xxx(n[:k]):
            for m2 in xxx(n[k+2:]):
                r.append(m1+al(n[k:k+2])+m2)

    return set(r)

print(xxx(1123))

def make_str(num):
    if len(num) == 1:
        return [chr(int(num) + 96)]
    else:
        result = ['']
        for original in num:
            result[0] += chr(int(original) + 96)
        for add in range(len(num) - 1):
            if int(num[add] + num[add + 1]) <= 26:
                front = result[0][:add] + chr(int(num[add] + num[add + 1]) + 96)
                if len(num[add:]) > 2:
                    possible = make_str(num[add + 2:])
                    for combine in possible:
                        result.append(front + combine)
                else: result.append(front)
        return result
print(make_str('1123'))

재귀로 풀었습니다.

    class Program
    {
        public static Dictionary<int, char> map = new Dictionary<int, char>();
        static void Main(string[] args)
        {
            for (int i = 1; i <= 26; i++)
            {
                map[i] = (char)('a' + (i - 1));
            }
            string alphaStr = Console.ReadLine();
            PrintCodes(string.Empty, alphaStr);
            Console.ReadKey();
        }

        public static void PrintCodes(string codePrefix, string subStr)
        {
            if (subStr.Length == 0)
                Console.WriteLine(codePrefix);

            for (int i = 1; i <= 2; i++)
            {
                if (i > subStr.Length)
                    break;
                else if (i == subStr.Length && int.Parse(subStr) <= 26)
                    Console.WriteLine(codePrefix + map[int.Parse(subStr)].ToString());
                else
                {
                    string newStr = subStr.Substring(0, i);
                    if (int.Parse(newStr) <= 26)
                    {
                        string codePre = map[int.Parse(newStr)].ToString();
                        PrintCodes(codePrefix + codePre, subStr.Substring(i));
                    }
                }
            }
        }
    }

spliter=' ,'
alp='abcdefghijklmnopqrstuvwxyz'

while True:

    number=input("Input numbers: ")

    def changesplit(n):
        str=''
        while n>0:
            str=spliter[n%2]+str
            n=n//2
        while len(str)<len(number)-1:
            str=' '+str
        return str

    splitlist=[]
    for i in range(2**(len(number)-1)):
        splitlist.append(changesplit(i))

    for split in splitlist:
        string=''
        for i in range(len(number)-1):
            string=string+number[i]+split[i]
        string=string+number[-1]
        string=string.replace(' ','')
        string=string.split(',')
        numlist=[]
        for i in string:
            numlist.append(int(i))
        test=1
        for i in numlist:
            if i<1 or i>26:
                test=0
        if test:
            for i in numlist:
                print(alp[i-1],end='')
            print('\n')

alphabets = {x-96 : chr(x) for x in range(97, 123)}

def search(sol, s):
  if not s:
    print(sol)
    return  
  search(sol + alphabets[int(s[0])], s[1:])
  if 10 <= int(s[:2]) <= 26:
    search(sol + alphabets[int(s[:2])], s[2:])


search('', '1123')

import re

def cases(o) :
#스트링을 입력으로 받아, 처음 숫자가 나오는 인덱스를 정규 표현식으로 찾는다. 교환 가능한 모든 경우의 수를 튜플의 형태로 반환한다.
    alp = 'abcdefghijklmnopqrstuvwxyz'
    s, mo = re.compile("[1234567890]+"), re.compile("[abcdefghijklmnopqrstuvwxyz]+")
    k,k_1, ret, ret_1 = s.findall(o), mo.findall(o), [], []
    if k and len(k[0]) >= 1 : ret.append(k[0][0])
    if k and len(k[0]) >= 2 and 26 > int(k[0][:2]) : ret.append(k[0][:2])  # 각각의 다음 노드(존재할 시)
    for u in ret :
        pre = s.sub(alp[int(u)-1], u)
        ret_1.append("".join(k_1)+pre+k[0][len(u):])
    return ret, ret_1

def IntToString(string) :
    res = [str(string)]
    while len(res) != 0 :
        po_data = res.pop()
        ca_res_1, ca_res_2 = cases(po_data)
        if len(ca_res_1) == 0 : print(po_data)
        for e in ca_res_2 :
            res.append(e) # res의 끝에 다음 노드를 추가

IntToString(int(input("INPUT : ")))

다른 분들의 풀이를 보니 제 풀이가 썩 훌륭한 풀이인 것 같지는 않지만, 백트래킹 공부한다고 생각하고 작성해 보았습니다.

결과

INPUT : 1123
kw
kbc
alc
aaw
aabc

숫자를 리스트화 하여 홀수번째 인덱스에 " "(스페이스)를 넣고 그 안에 ","(콤마)나 ""(공백)을 넣어서 재귀로 풀었습니다.

inp="1123"
alpha=" abcdefghijklmnopqrstuvwxyz" #alpha[1]="a",..., alpha[26]="z"
lst=list(inp)
for i in range(len(inp)-1):
    lst.insert(2*i+1," ") #숫자를 리스트화 한 것의 홀수번째 인덱스에 " "(스페이스) 삽입
cob=[",",""] #콤마 또는 ""(공백) #홀수번째 인덱스에 삽입하기 위함
i=1 #인덱스
def solve(lst):
    global i
    if i==len(lst): #마지막 홀수번째 인덱스에 ","(콤마)나 ""(공백)을 넣고 나면 +2가 되므로 i는 len(lst)와 같아짐
        ans,s="","".join(lst) #ans:정답을 받기위한 빈 문자열, s=lst를 문자열로 변환한 것
        slst=s.split(",") #s를 다시 ","(콤마)를 기준으로 리스트화
        try: #slst안의 숫자가 alpha의 인덱스를 초과할 수도 있기에 try구문 사용
            for num in slst:
                ans+=alpha[int(num)]
            print(ans)
        except:
            pass
        return
    else:
        for ins in cob:
            lst[i]=ins
            i+=2
            solve(lst)
            i-=2
            lst[i]=" "
solve(lst)

출력

#inp="1123"일 때
aabc
aaw
alc
kbc
kw

#inp="12345"일 때
abcde
awde
lcde

(def n:ch (zipmap (map str (range 1 27))
                  "abcdefghijklmnopqrstuvwxyz"))

(defn nseq
  ([n] (nseq n []))
  ([n v] (cond (= n 0) [v]
               (= n 1) [(conj v 1)]
               :else (into (nseq (- n 1) (conj v 1))
                           (nseq (- n 2) (conj v 2))))))

(defn ranges [v]
  (partition 2 1 (reductions + 0 v)))

(defn strseq [inp]
  (let [s (str inp)]
    (->> (nseq (count s))
         (map ranges)
         (map #(map (fn [[beg end]] (subs s beg end)) %))
         (map #(map (fn [s] (n:ch s)) %))
         (filter #(every? some? %))
         (map #(apply str %)))))

(strseq 1123) ;=> ("aabc" "aaw" "alc" "kbc" "kw")
(strseq 1234) ;=> ("abcd" "awd" "lcd")
(strseq 11111) ;=> ("aaaaa" "aaak" "aaka" "akaa" "akk" "kaaa" "kak" "kka")

Clojure 부흥위원회에서 나왔읍니다
답들을 돌아보니 Clojure 코드도 있던데 단순 알고리즘에 atom을 쓰셨길래 저도 한번 짜 봤읍니다

핵심은 nseq 재귀함수입니다. 요새 재귀를 짠지 오래되서 살짝 헤맸는데, 트리를 그려보고

[남은수  선택1or2]
4 - [3 1] - [2 1] - [1 1] - [0 1] ... 1111
  |       |       |
  |       |       - [0 2] ........... 112
  |       |
  |       - [1 2] - [0 1] ........... 121
  |
  - [2 2] - [1 1] - [0 1] ........... 211
          |
          - [0 2] ................... 22

(nseq 4) = [(nseq 3), (nseq 2)]로 표현된다는 걸 힌트로, 수식을 함수로 그대로 표현했습니다.
그 다음은 그냥 근로저스럽게 idiomatic하게 짰습니다. 더 간결할 수 있을지도 모르겠는데 걍 대충 했습니다.

재귀 함수는 위에서 아래로, 모르는 계산은 함수에게 떠넘긴다는 느낌으로 작성하면 쉽습니다.
자세한 내용은 제 블로그에서..

감사합니다 and I also 근로저 조아

KUR (a.k.a 츄럴@깃갤)

def ord_chr(ans, string):
    if len(string)==0:
        print(ans)
        return None
    if len(string)==1:
        print(ans + chr(ord('a')+int(string)-1))
        return None

    ord_chr(ans+chr(ord('a')+int(string[0])-1), string[1:])
    if int(string[0:2]) <= 26:
        ord_chr(ans+chr(ord('a')+int(string[0:2])-1), string[2:])


inp = input('>>>')
ord_chr('', inp)

JAVA입니다.

package question2.숫자로_만드는_문자열;

import java.util.ArrayList;
import java.util.List;

public class NumberSplitter {
    String number;
    List<List<Integer>> splits; //숫자를 분할 가능한 모든 조합

    public NumberSplitter(String number) {
        this.number = number;
        this.splits = new ArrayList<List<Integer>>();
    }

    void split(String numStr, List<Integer> splitted) {
        //숫자를 한 글자 또는 두 글자로 분할하는 조합을 찾는 재귀함수
        if(numStr.length() <= 1) {
            int value = Integer.parseInt(numStr);
            if(value == 0) {
                //0은 알파벳으로 변환되지 않음
                return;
            }
            splitted.add(value);
            splits.add(splitted);
        }
        else {
            int value1 = Integer.parseInt(numStr.substring(0, 1));
            int value2 = Integer.parseInt(numStr.substring(0, 2));

            List<Integer> newSplitted = new ArrayList<Integer>();
            newSplitted.addAll(splitted);
            newSplitted.add(value2);

            if(numStr.length() == 2) {
                if(value2 > 0 || value2 <= 26) {
                    //실제 알파벳
                    splits.add(newSplitted);
                }
                else {
                    //알파벳이 아님
                    return;
                }
            }
            else {
                split(numStr.substring(2), newSplitted);
            }

            splitted.add(value1);
            split(numStr.substring(1), splitted);
        }
    }
    void split(String numStr) {
        //오버로딩
        split(numStr, new ArrayList<Integer>());
    }
}

package question2.숫자로_만드는_문자열;

import java.util.List;

public class NumToString {

    public static void main(String[] args) {
        String input = "1123";

        final char[] alphabets = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k',
            'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};

        NumberSplitter ns = new NumberSplitter(input);
        ns.split(input);

        for (List<Integer> split : ns.splits) {
            String output = "";
            for (int c : split) {
                output = output + alphabets[c-1];
            }
            System.out.println(output);
        }
    }
}