Solving the Permutations Problem using Backtracking in Java

Sai Kathiroli — Tue, 05 Dec 2023 06:56:07 +0000

Introduction:
The "Permutations" problem on LeetCode challenges us to generate all possible permutations of a given set of distinct integers. In this article, we'll explore an effective solution to this problem using backtracking in Java.

Understanding the Problem:
The goal is to generate all possible permutations of the given array of integers. A permutation is an arrangement of all the elements in a set. The key here is that all permutations should be unique.

Approach:
We will use a backtracking approach to explore all possible combinations and construct permutations. Backtracking is a systematic way of exploring all possible solutions to a problem and undoing a choice if it doesn't lead to a valid solution.

Code Walkthrough:
Let's dive into the provided Java code and understand how it works.

class Solution {
    List<List<Integer>> ass = new ArrayList<>();

    public List<List<Integer>> permute(int[] nums) {
        List<Integer> one = new ArrayList<>(nums.length);
        for(int x:nums) {
            one.add(Integer.MIN_VALUE);
        }
        permu(nums, 0, nums.length, one);
        return ass;
    }

    public void permu(int[] nums, int a, int e, List<Integer> was) {
        if(a == e) {
            ass.add(was);
            return;
        }
        for(int i = 0; i < nums.length; i++) {
            if(was.get(i) == Integer.MIN_VALUE) {
                List<Integer> monk = new ArrayList<>(was);
                monk.set(i, nums[a]);
                permu(nums, a + 1, e, monk);
            }
        }
    }
}

List Initialization: The ass list is used to store the final result, i.e., all permutations.

permute() Method: This method initializes a list one with a placeholder value (Integer.MIN_VALUE) and then calls the permu() method to start the permutation generation process.

permu() Method: This is the recursive backtracking method. It checks if the current permutation is complete (a == e) and adds it to the result list. Otherwise, it iterates through the elements of the input array, makes a choice, and recurses.

Improvements and Explanation:
While the provided code successfully generates permutations, there is an issue with the way lists are handled. In Java, when you add a list to another list (ass.add(was)), you are essentially adding a reference to the same list. This can lead to unintended behavior, as modifications to one list will affect others.

To fix this, we should create a deep copy of the list before adding it to the result. Replace the line ass.add(was) with ass.add(new ArrayList<>(was)) to ensure that each permutation is stored independently.

ass.add(new ArrayList<>(was));

Conclusion:
In this article, we explored a backtracking approach to solving the "Permutations" problem on LeetCode using Java. We analyzed the provided code, explained the backtracking strategy, and suggested an improvement to handle list references correctly. Understanding and implementing backtracking is a valuable skill for solving a wide range of combinatorial problems.

Navigating the Coding Challenge Seas: Unraveling the Search in Rotated Sorted Array Puzzle

Sai Kathiroli — Thu, 30 Nov 2023 15:43:04 +0000

Hey Dev.to community! 👋 Today, I'm thrilled to share a recent triumph in the coding realm – solving the LeetCode problem "Search in Rotated Sorted Array".

The Challenge:
The task at hand involved searching for a target element in a rotated, sorted array. Sounds tricky, right? But fear not, as I dove into the problem armed with a Java implementation and a strategic algorithm.

The Algorithm:
Let's break down the thought process behind the solution:

// Java code snippet
public class D1 {
    public static void main(String[] args) {
        // Given rotated sorted array
        int[] nums = {4,5,6,7,0,1,2};
        int target = 0;
        int low=0;
        int high=nums.length-1;
        int result=-1;

        while(low<=high) {
            // Binary search implementation
            int mid = high+(low-high)/2;
            if(nums[mid] == target) {
                result = mid;
                break;
            }

            // Check if the left part is sorted
            if(nums[low] <= nums[mid]) {
                // Check if there is a possibility that the target exists here
                if(nums[low] <= target && target <= nums[mid]) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            } else {
                // Check if there is a possibility that the target exists here
                if(target <= nums[high] && nums[mid] <= target) {
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
        }

        System.out.println(result);
    }
}

The algorithm cleverly narrows down the search space by identifying sorted portions of the rotated array and zeroing in on the potential location of the target.

Resources and Learning:
To solidify my understanding and approach, I delved into other valuable resources:
https://www.youtube.com/watch?v=U8XENwh8Oy8
https://takeuforward.org/data-structure/search-element-in-a-rotated-sorted-array/
These resources provided additional insights and perspectives, contributing to a holistic grasp of the problem.

As I share this accomplishment, I'm eager to connect with the Dev.to community. Your feedback, thoughts, and alternative approaches are not just welcomed but encouraged. Let's learn and grow together!

This coding journey is a testament to my commitment to professionalism, continuous learning, and problem-solving skills. The ability to navigate complex challenges is not just a technical feat but a demonstration of adaptability and perseverance.

DEV Community: Sai Kathiroli

Solving the Permutations Problem using Backtracking in Java

Navigating the Coding Challenge Seas: Unraveling the Search in Rotated Sorted Array Puzzle