15 ms Java DFS, using a function to check for duplicate


  • 0
    C

    15 ms, DFS, 30 lines, using a function to check for duplicate in the array.

    public class Solution {
        public List<List<Integer>> findSubsequences(int[] nums) {
            List<List<Integer>> all = new ArrayList<>();
            List<Integer> path = new ArrayList<>();
            dfs(nums, 0, nums.length, path, all);
            return all;
        }
        
        private void dfs(int [] nums, int start, int end, List<Integer> path, List<List<Integer>> all) {
            if (path.size() >= 2) {
                all.add(new ArrayList<>(path));
            }
            for (int i = start; i < end; ++i) {
                if ((path.size() == 0 || nums[i] >= path.get(path.size() - 1)) && !hasDuplicate(nums, start, i)) {
                    path.add(nums[i]);
                    dfs(nums, i + 1, end, path, all);
                    path.remove(path.size() - 1);
                }
            }
        }
        private boolean hasDuplicate(int [] nums, int start, int index) {
            for (int i = start; i < index; ++i) {
                if (nums[i] == nums[index]) {
                    return true;
                }
            }
            return false;
        }
    }
    

Log in to reply
 

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