Сложность времени этой рекурсивной функции

Question

У меня есть эта рекурсивная функция. Я хочу знать временную сложность этого алгоритма. Идея дается ряд, мы должны найти все подмножества, что сумма в поддавки числа

public void getSequences(int n, ArrayList<Integer> buffer, int sum) { 
    if(sum == n) { 
    for(int j=0; j<buffer.size(); j++) { 
     System.out.print(buffer.get(j) + " "); 
    } 
    System.out.println(""); 
    } 

    for(int i=1; i<n; i++) { 
    sum += i; 
    if(sum > n) { 
     break; 
    } 
    buffer.add(i); 
    getSequences(n, buffer, sum); 
    sum -= i; 
    buffer.remove(i); 
    } 
} 

ArrayList<Integer> buffer = new ArrayList<Integer>(); 
getSequences(3, buffer, 0); 

// Output 
// 1 1 1 
// 1 2 
// 2 1 

Какова временная сложность этого алгоритма?

Answer 1

Поскольку код генерирует каждую возможную последовательность, которая суммируется с n, и потому что порядок имеет значение. Асимптотическая сложность связана с размером последовательностей.

Другой способ подсчета всех последовательностей состоит в следующем.

1. n 1 с.

   Пример: 1 1 1 1 1

2. В течение некоторого BitSet длины n-1, уменьшить соседние последовательности, если бит включен для этого индекса.

   Пример: BitSet (0,1,0,0) дает последовательность: 1 (1 + 1), 1 = 1> 1 2 1 1

   Пример: (1,1,0,1) дает BitSet последовательность: (1 + 1 + 1) (1 + 1) => 3 2

Так как специфический BitSet размера n-1 дает уникальную последовательность, то этот алгоритм, очевидно, O (2^п).