[dfs] how to deal with duplicates? 491. Increasing Subsequences

Given an integer array, your task is to find all the different possible increasing subsequences of the given array, and the length of an increasing subsequence should be at least 2 .

Example:
Input: [4, 6, 7, 7]
Output: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]
Note:
The length of the given array will not exceed 15.
The range of integer in the given array is [-100,100].
The given array may contain duplicates, and two equal integers should also be considered as a special case of increasing sequence.

容易看出这是dfs的问题。
容易写出以下dfs的过程:

    public List<List<Integer>> findSubsequences(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        helper(nums, 0, res, new ArrayList<Integer>());
        return res;
    }
    
    private void helper(int[] nums, int index, List<List<Integer>> res, List<Integer> list) {
        if (list.size() >= 2) {
            res.add(new ArrayList<Integer>(list));
        } 
        
        for (int i = index; i < nums.length; i++) {
            if (list.size() == 0 || nums[i] >= list.get(list.size() - 1)) {
                list.add(nums[i]);
                helper(nums, i + 1, res, list);
                list.remove(list.size() - 1); // 有和没有当前数字参与两种选择
            }
        }
    }

一个问题,如何避免duplicate?例如[4,6,7,7],[4,6,7]已经加上了,如何避免再加一次?
可以用以下简单方法:不同层recursion中,保证单次recursion调用每个数字只循环到一次。例如,[4,6,7,7]中,当前这次调用的循环中,已经循环到了4,6,7,再遇到7,就不管了。看以下code:

    public List<List<Integer>> findSubsequences(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        helper(nums, 0, res, new ArrayList<Integer>());
        return res;
    }
    
    private void helper(int[] nums, int index, List<List<Integer>> res, List<Integer> list) {
        if (list.size() >= 2) {
            res.add(new ArrayList<Integer>(list));
        } 
        
        Set<Integer> unique = new HashSet<Integer>();
        for (int i = index; i < nums.length; i++) {
            if (list.size() == 0 || nums[i] >= list.get(list.size() - 1)) {
                if (!unique.add(nums[i])) continue;//对当前循环相同数字只能用一次 
                unique.add(nums[i]); //记录当前循环到的数字,用当前list再去递归的不用想
                list.add(nums[i]);
                helper(nums, i + 1, res, list);
                list.remove(list.size() - 1);
            }
        }
    }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s