섹션 8의 13번 수열의 추측 시간복잡도 질문 있습니다.

선생님 조합수를 사용해도 시간복잡도는 O(n!)인거 같은데 제가 잘못 생각한걸까요?

조합수를 사용하지 않아도 메모이제이션을 사용하면 O(n!)인거 같아서 질문 드립니다.

혹시 맞으면 시간복잡도를 O(n^k)정도로 바꿀 수 있는 방법이 있을까요?

조합수를 사용하지 않은 풀이입니다. 비효율적인 부분이나 잘못된점도 알고 싶습니다.

 function solution(n, f){
                const arrayMaker = (len, generator) => 
                    Array.from({ length: len}, (_, i) => generator(i));
                const base = arrayMaker(n, idx => idx + 1);
                const checker = arrayMaker(n, () => 0);
                const temp = arrayMaker(n, () => 0);
                const change = i => array => array[i] === 0 ? array[i] = 1 : array[i] = 0;

                function *permutation (position){
                    if(position === n){
                        yield temp;
                    }
                    else{
                        for(let i = 0; i < checker.length; i++){
                            if(checker[i] === 0){
                                temp[position] = base[i];
                                change(i)(checker);
                                yield *permutation(position + 1);
                                change(i)(checker);
                            }
                        }
                    }
                }         
                                
                function combination (n, r, seq){
                    if(bin[n - 1][r - 1] !== 0) return bin[n - 1][r - 1];
                    if(n === 1) return seq[r-1];
                    return bin[n - 1][r - 1] = combination(n - 1, r, seq) + combination(n - 1, r + 1, seq);
                }
                let bin;
                for(let order of permutation(0)){
                    bin = arrayMaker(n, () => arrayMaker(n, () => 0));
                    if( combination(n, 1, order) === f) return order;
                }
            }
            console.log(solution(4, 16));

인프런 커뮤니티 질문&답변