Will this solution has equal space complexity of the recursion one?


  • 0
    3

    Here is my iterative solution -- for i = 1 to n-1, each loop will generate all permutations of length i + 1 based on the permutations of length i. Will the space complexity be worse or be better than a recursive solution? Could it be improved somehow?

     public List<List<Integer>> permute(int[] num) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (num == null || num.length == 0) // return if trivial
            return result;
        // add num[0] into result list, since it's the only permutation case of length 1
        List<Integer> list = new ArrayList<Integer>();
        list.add(num[0]);
        result.add(list); 
        int n = num.length;
        for (int i = 1; i < n; i++) // for v = num[1], num[2], ... num[n-1], 
        {
            int v = num[i];
            int m = result.size();
            // generate all permutations of length i+1 
            for (int j = 0; j < m; j++) 
            {
                list = result.get(j);
                int o = list.size();
                // by inserting v into each possible insertion point k of every permutations of length i
                for(int k = 0; k <= o; k++) 
                {
                    ArrayList<Integer> permutation = new ArrayList<Integer>(list);
                    permutation.add(k, v);
                    result.add(permutation);
                }
            }
            // delete all permutations of length i from the result list
            for(int j = 0; j < m; j++) 
            {
                result.remove(0);
            }
        }
        return result;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.