是否爲空間複雜度返回值帳戶

Question

下面是用於生成多個集合的算法。正是它解決了以下問題Print all combination of element in the array such that first element of array is d and next element in the array can be +1 or -1 the previous element in the array. Code was required. Input: num=4, level=3. Output - 4, 3, 2 || 4, 3, 4 || 4, 5, 4 || 4, 5, 6。

此問題未使用int[] arr = new int[level]作爲最終被複制到int數組列表中的數據存儲。

以下代碼的空間複雜度是多少？它是O（級別），即用於解決問題的存儲，還是O（2^level-1），即返回類型的大小？

public static List<int[]> getCombinations(int num, int level) { 
     final List<int[]> combinations = new ArrayList<int[]>(); 
     int[] arr = new int[level]; 
     computeCombinations(num, level - 1, 0, combinations, arr); // note : its level - 1, since currentlevel is set to 0. 
     return combinations; 
    } 


    private static void computeCombinations(int num, int level, int currLevel, List<int[]> list, int[] arr) { 
     arr[currLevel] = num; 

     if (currLevel == level) { 
      // list.add(arr); <- wrong to do it so 
      int[] temp = new int[arr.length]; 
      System.arraycopy(arr, 0, temp, 0, arr.length); 
      list.add(temp); 
      return; 
     } 

     computeCombinations(num - 1, level, currLevel + 1, list, arr); 
     computeCombinations(num + 1, level, currLevel + 1, list, arr); 
    } 

Answer 1

空間複雜佔活存儲器由算法使用的量，因此ArrayList<int[]>因素的複雜性。但是，在帖子頂部給出的算法說明表明，您只需要打印組合，而不是返回;如果您在創建組合後立即打印出組合，然後放棄它們（即破壞性地更新組合而不是複製組合），那麼您將提高空間複雜度。