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

function solution(k, nums, m) {
  const isMulti = (n, m) => {
    if (!(n % m)) return 1;
    return 0;
  };

  let ans = 0;

  function DFS(L, sp, sum) {
    if (L === k) {
      console.log(L, tmp, sp, sum);
      if (isMulti(sum, m)) ans++;
    } else {
      for (let i = sp; i < nums.length; i++) {
        DFS(L + 1, i + 1, sum + nums[i]);
      }
    }
  }
  DFS(0, 0, 0);
  return ans;
}

해당 문제 시간복잡도가 궁금하여 질문드립니다.
해당 문제를 선생님과 똑같이 풀이했는데요, DFS 내부 for문의 i시작점이 동적으로 변하다보니 시간복잡도를 어떻게 잡아야 할지 몰라 헷갈려 질문드려요.

만일 for문의 i의 시작점이 고정적으로 0이라면 O(N^K)가 될 것 같은데,
이처럼 i가 유동적으로 변하는 것으로 기존 빅오 표기에 영향이 갈만큼 차이가 발생하게 되나요?

시간내어 확인해주셔서 감사합니다.