Java Backtrack Solution


  • 1
    Z
    public class Solution {
        public List<List<Integer>> findSubsequences(int[] nums) {
            List<List<Integer>> allSol = new ArrayList<>();
            if (nums == null || nums.length <= 1) {
                return allSol;
            }
            List<Integer> sol = new ArrayList<>();
            Set<List<Integer>> allSolSet = new HashSet<>();
            findSub(nums, 0, sol, allSolSet); 
            for (List<Integer> list : allSolSet) {
                allSol.add(list);
            }
            return allSol;
        }
        
        public void findSub(int[] nums, int start, List<Integer> sol, Set<List<Integer>> allSol) {
            if (sol.size() >= 2) {
                allSol.add(new ArrayList<Integer>(sol));
            }
            if (start >= nums.length) {
                return;
            }
            
            for (int i = start; i < nums.length; i++) {
                if (sol.size() == 0 || nums[i] >= sol.get(sol.size() - 1)) {
                    sol.add(nums[i]);
                    findSub(nums, i + 1, sol, allSol);
                    sol.remove(sol.size() - 1);
                } else {
                    findSub(nums, i + 1, sol, allSol);
                }
            }
        }
    }
    

    Manage to pass the test, but I have to use a set to remove duplicate, which is not desirable. Just for reference.


Log in to reply
 

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