package main

import (
    "fmt"
)

func main() {
    result := out([]string{"1","2","3","4","5","6"})
    fmt.Println(result)
	
	fmt.Println("total :", len(result))
	fmt.Println("should :", 6*5*4*3*2 )
	//fmt.Println("should :", 6*5*4*3*2 + 5*4*3*2 + 4*3*2 + 3*2 + 2)
}

func compbine(str []string) []string{
	
	rst := []string{}
	for i:=1 ; i<len(str) ; i++ {
		sub := out(str[:i])
		rst = append(rst, sub...)
	}
	return rst
}

func out(str []string) []string {
    
	length := len(str)
    
    if length == 1 {
        return []string{str[0]}
    }

    return insert(out(str[:length-1]), str[length-1])
}

func insert(res []string, num string) []string {
    
    result := make([]string, len(res)*(len(res[0])+1))

    index := 0
    for _, v := range res {
        for i := 0; i < len(v); i++ {
            result[index] = v[:i] + num + v[i:]
            index++
        }
        result[index] = v + num
        index++
    }

    return result
}