Why this code exceeds time limit


  • 0
    L

    This is my straight forward solution, I think the running time is O(2^n). But OJ gives me "exceeds time limit" on test case [1, 2, 3, 4, 5, 6, 7, 8, 9, 0].
    I don't see any difference between my implementation and the one here: https://leetcode.com/discuss/63913/solution-java-but-dont-know-why-have-create-new-list-on-line-14
    . The interesting thing is the implementation above does not cause a exceeds time limit error. Any one has clue on what is going on here?

    Thanks

    
    public class Solution {
        public List<List<Integer>> subsets(int[] nums) {
            List<List<Integer>> result = new ArrayList<List<Integer>>();
            List<Integer> list = new ArrayList<>();
            
            if (nums == null || nums.length == 0) {
                return result;
            }
            Arrays.sort(nums);
            subsetsHelper(nums, list, result, 0);
            return result;
        }
        
        private void helper(int[] nums, List<Integer> list, List<List<Integer>> result, int index) {
            result.add(new ArrayList<Integer>(list));
            
            for (int i = index; i < nums.length; i++) {
                list.add(nums[i]);
                helper(nums, list, result, index + 1);
                list.remove(list.size() - 1);
            }
        }
    }

Log in to reply
 

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