Share my 12-line simple java code with brief explanations


  • 13
    M
    /*
        dfs. 每个位置都有选与不选两个选项, 也可以看成遍历一棵二叉树, 向左走选, 向右走不选
    */
    public class Solution {
        public List<List<Integer>> subsets(int[] nums) {
            List<List<Integer>> ans = new ArrayList<>();
            if (nums == null) { return ans; }
            Arrays.sort(nums);  // non-descending order
            dfs(ans, nums, new ArrayList<Integer>(), 0);
            return ans; 
        }
        
        private void dfs(List<List<Integer>> ans, int[] nums, List<Integer> list, int index) {
            if (index == nums.length) { ans.add(new ArrayList<Integer>(list)); return; }
            dfs(ans, nums, list, index+1);  // not pick the number at this index
            list.add(nums[index]);
            dfs(ans, nums, list, index+1);  // pick the number at this index
            list.remove(list.size()-1);
        }
    }

  • 6
    S

    中文解释,666666666666666666666666666


  • 0
    M

    ............upvoted


  • 0
    D
    This post is deleted!

  • 0
    I

    Why do you have to remove from the list after picking the number at the index?


  • 0
    M

    Because you are picking(trying) each number AT THIS RECURSION LEVEL. One index corresponds to one level. For example, at index 2, the array is like [already-picked-number-0, already-picked-number-1, -(currently-trying)-, not-yet-picked-number-0,...]. Suppose we are trying 45 at "currently-trying", after 45 and the following recursion levels are done, if we do not remove 45 at currently-trying, and add 46 directly, the array will be like [already-picked-number-0, already-picked-number-1, 45, 46,...]. what we want is [already-picked-number-0, already-picked-number-1, 46, not-yet-picked-number-0,...]


  • 0
    I

    But for the powerset of a string, I can just do it like this without removing any characters:

    def powersetString(curr_subset, s):
        if not s:
            print curr_subset
        else:
            powersetString(curr_subset + s[0], s[1:])
            powersetString(curr_subset, s[1:])
    

    Why do I have to pop it out if it is a list?


  • 0
    M

    yeah, indeed. as to a string, you just did not remove the previously tried characters MANUALLY BY YOURSELF, the virtual machine does that for you. this is because string is stored in the stack frame, not in the dynamically allocated memory(heap). for each recursion level, there is one corresponding stack frame, in which there is one current version of the string. when you backtrack from a deeper recursion level(current) to the previous recursion level, current stack frame dies, the string stored in the current stack frame dies, previous stack frame becomes active, and so does the string stored in it. you may search "call stack" online to get more information.


  • 0
    M

    therefore, there are in fact multiple copies of strings of different states in the entire process of recursion, which is not efficient. in java, you can use a StringBuilder, whose content is stored in the heap, thus you should add and remove characters manually. in this way, there is only one copy of the string, it's just that its content keeps changing.


Log in to reply
 

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