Clean 20ms solution


  • 16
    S
    public List<List<Integer>> findSubsequences(int[] nums) {
    	List<List<Integer>> res = new ArrayList<>();
    	helper(res, new ArrayList<Integer>(), nums, 0);
    	return res;
    }
    	
    private void helper(List<List<Integer>> res, List<Integer> list, int[] nums, int id) {
    	if (list.size() > 1) res.add(new ArrayList<Integer>(list));
    	List<Integer> unique = new ArrayList<Integer>();
    	for (int i = id; i < nums.length; i++) {
    		if (id > 0 && nums[i] < nums[id-1]) continue; // skip non-increase
    		if (unique.contains(nums[i])) continue; // skip duplicate
    		unique.add(nums[i]);
    		list.add(nums[i]);
    		helper(res, list, nums, i+1);
    		list.remove(list.size()-1);
    	}
    }
    

  • 3
    Y

    @shawloatrchen you can also use set for unique check:

    List<Integer> unique = new ArrayList<Integer>();
    

    to

    Set<Integer> unique = new HashSet<>();
    

    and

    		if (unique.contains(nums[i])) continue; // skip duplicate
    		unique.add(nums[i]);
    

    to

    if(!unique.add(nums[i])) continue;
    

  • 0
    S

    @yuhaowang001 yes, you're right


  • 1
    R

    Python version:

    class Solution(object):
        def findSubsequences(self, nums):
            def helper(res, arr, nums, i):
                if len(arr) > 1:
                    res.append(list(arr))
                unique = []
                for k in xrange(i, len(nums)):
                    if i > 0 and nums[k] < nums[i-1]:
                        continue
                    if nums[k] in unique:
                        continue
                    arr.append(nums[k])
                    unique.append(nums[k])
                    helper(res, arr, nums, k + 1)
                    arr.pop()
                    
            res = []
            helper(res, [], nums, 0)
            return res
    

    Javascript:

    var findSubsequences = function(nums) {
        var res = [];
            helper(res, [], nums, 0);
            return res;
    };
    
    var helper = function(res, list, nums, id) {
            if(list.length > 1) res.push(list.slice());
            var unique = [];
            for(var i = id; i < nums.length; i++) {
                if(id > 0 && nums[i] < nums[id-1]) continue;
                if(unique.indexOf(nums[i]) >= 0) continue;
                unique.push(nums[i]);
                list.push(nums[i]);
                helper(res, list, nums, i+1);
                list.pop()
            }
    }
    

  • 0

    @shawloatrchen can you explain the code? Thank you.


  • 0
    R

    @bo28 said in Clean 20ms solution:

    @shawloatrchen can you explain the code? Thank you.

    He's using recursive DFS and keeping a count of the uniques to prevent duplicate processing only if the number is increasing


  • 0
    C

    How can that List<Integer> unique be used to prevent duplicate processing ?? I'm quite confused with that one. Thanks

    For example, my c++ code below for

    Your input

    [4,6,7,7]
    Your stdout

    i is 0
    i is 1
    i is 2
    i is 3
    i is 3
    7
    i is 2
    6
    i is 3
    i is 3
    7
    6
    i is 1
    4
    i is 2
    i is 3
    i is 3
    7
    i is 2
    6
    4
    i is 3
    i is 3
    7
    6
    4

    class Solution {
    public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> path;
        
        dfs(res, path, nums, 0);
        return res;
    }
    
    void dfs(vector<vector<int>>& res, vector<int>& path, vector<int>& nums, int idx){
        if (path.size()>1)
            res.push_back(path);
            
        unordered_set<int> unique;
        
        for (int i=idx; i<nums.size(); i++){
            if (idx>0&&nums[i]<nums[idx-1])
                continue;
            cout<<"i is ";
            cout<< i<<endl;
            for (auto u: unique)
                cout<<u<<endl;
            
            if (unique.count(nums[i]))
                continue;
                
            unique.insert(nums[i]);
            path.push_back(nums[i]);
            dfs(res, path, nums, i+1);
            path.resize(path.size()-1);
        }
    }
    

    };


  • 0
    S

    @coder2 in each recursion, same value only use once,
    for example [1,5,1],
    the first recursion only considers 1 and 5, the last 1 is skipped.
    in recursion [1] the next value can either 5 or 1 so we have [1, 5] and [1,1]
    in recursion [5] the next option is only 1, but 1 < 5 , and size of [5] is less than 2.
    So, the final answer is [1,5] and [1,1];


  • 0
    C

    [1,5,1] would work for the following code, but [4,6,7,7] won't. I'm still confused.

    class Solution {
    public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
    vector<vector<int>> res;
    vector<int> path;

    dfs(res, path, nums, 0);
    return res;
    

    }

    void dfs(vector<vector<int>>& res, vector<int>& path, vector<int>& nums, int idx){
    if (path.size()>1){
    cout<<"path.size()>1, idx is ";
    cout<< idx <<endl;

        cout<<"path contains "<<endl;
        for (auto u: path)
            cout<<u<<endl;
            
            
         res.push_back(path);
    }
       
        
    unordered_set<int> unique;
    
    for (int i=idx; i<nums.size(); i++){
        if (idx>0&&nums[i]<nums[idx-1])
            continue;
        cout<<"i is ";
        cout<< i<<endl;
        
        cout<<"unique include "<<endl;
        for (auto u: unique)
            cout<<u<<endl;
        /*
        if (unique.count(nums[i])){
            cout<<"unique contains ";
            cout<< nums[i]<<endl;
            continue;
        }
        */
            
        unique.insert(nums[i]);
        path.push_back(nums[i]);
        dfs(res, path, nums, i+1);
        path.resize(path.size()-1);
    }
    

    }
    };


  • 0
    S

    @coder2 You code is accepted, why confusing


  • 0
    F

    very good dedup method


Log in to reply
 

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