[Help Please] Java Solution Prints Correctly, But Won't Return


  • 0

    I've spent about two hours poking around on this problem, and I finally got a solution that prints the right output. I've been trying to structure my code in such a way that I'd be able to return the correct output, but I'm failing to do so. I think my pitfall is that when I've found the correct output, my function continues to run on the other recursive stacks and therefore "messes up" the correct output. At least that's what I've seen from my analysis. If you could offer any advice and or code improvements for me, I would greatly appreciate it.

    My solution approach: use a mask and XOR to "flip" every single bit. This is the next "step" of the gray code. If this next step is already in the gray code then continue to next iteration. If this step is not in the gray code already then continue the backtrack and see if I can find the "completed" gray code. The completed gray code, I know, will have size max. Once I've found the list with size max, then I know that I have the correct gray code. If all iterations of the for loop run, then I know that I've reached a dead-end, so I remove the last "step" that was added and then the recursion continues.

    public class Solution {
        public List<Integer> grayCode(int n) {
            List<Integer> res = new ArrayList<Integer>();
            res.add(0);
            backtrack(res, 0, (int) Math.pow(2, n), n);
            return res; 
        }
        
        public void backtrack(List<Integer> res, int prev, int max, int n) {
            if(res.size() == max) {
                System.out.println(Arrays.toString(res.toArray()));
                return; 
            }
            for(int i = 0; i < n; i++) {
                int mask = 1 << i;
                int next = mask ^ prev;
                if(res.contains(next)) continue;
                res.add(next);
                backtrack(res, next, (int) Math.pow(2, n), n);
            }
            res.remove(res.size() - 1);
        }
    }
    

Log in to reply
 

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