palemgangireddy
BAN USER#include <stdio.h>
#include <malloc.h>
#define ROWS 4
#define COLS 5
int exists_path(int** matrix, int currx, int curry, int endx, int endy, int maxx, int maxy)
{
if (currx < 0 || currx > maxx)
return 0;
if (curry < 0 || curry > maxy)
return 0;
if (currx == endx && curry == endy)
return 1;
if (matrix[currx][curry] == 1)
return 0;
//printf("%0d %0d %0d %0d\n", currx, curry, endx, endy);
matrix[currx][curry] = 1;
return exists_path(matrix, currx+1, curry, endx, endy, maxx, maxy) ||
exists_path(matrix, currx-1, curry, endx, endy, maxx, maxy) ||
exists_path(matrix, currx, curry+1, endx, endy, maxx, maxy) ||
exists_path(matrix, currx, curry-1, endx, endy, maxx, maxy);
}
int main()
{
int** matrix;
matrix = malloc(sizeof(int*) * ROWS);
int i,j;
for (i = 0; i < ROWS; i++)
{
matrix[i] = malloc(sizeof(int) * COLS);
}
for(i = 0; i < ROWS; i++)
{
for (j = 0; j < COLS; j++)
matrix[i][j] = 0;
}
matrix[0][2] = 1; matrix[0][4] = 1;
matrix[2][1] = 1; matrix[2][2] = 1; matrix[2][3] = 1; matrix[2][4] = 1;
matrix[3][1] = 1; matrix[3][2] = 1;
for(i = 0; i < ROWS; i++)
{
for (j = 0; j < COLS; j++)
printf("%0d ", matrix[i][j]);
printf("\n");
}
int path = exists_path(matrix, 1, 4, 3, 0, 3, 4);
printf("Hello, World! %0d\n", path);
return 0;
}
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void permutation(String str) {
permutation("", str);
}
private static void permutation(String prefix, String str) {
int n = str.length();
if (n == 0) isWellOrdered(prefix);
else {
for (int i = 0; i < n; i++)
permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
}
}
private static void isWellOrdered(String permute) {
char[] c = permute.toCharArray();
int len = c.length;
for (int i = 0; i < len; i++)
{
for (int j = i; j < len; j++)
{
if (c[j] < c[i]) return;
}
}
System.out.println(permute);
}
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
String str = "abcd";
System.out.println("Input char seq is"+str);
permutation(str.toLowerCase());
}
}
- palemgangireddy January 11, 2015
1. Initialize a bitmap array of size N to 0. Initialize a count variable to 0.
- palemgangireddy August 07, 20152. Run through the power set of input array, and for every element in power set - sum all elements and set corresponding location in bitmap array.
3. Check if all indices are set in bitmap array. If yes, return count
4. Add first index set to 0 in bitmap to input array. Set this bitmap index. Increment count. Run all combinations of input array with this element - size of 2, 3.. etc and set the bitmap. Go to step 3.
Complexity: O(min(N, 2^array_size)*logN)
Memory: O(N)
Eg: N = 4, input array {}
After iteration 1: add 1. Covers 1
After iteration 2: add 2. Covers 2, 3
After iteration 3: add 4. Covers 4
O(NlogN) in this case.